結果

問題 No.2667 Constrained Permutation
コンテスト
ユーザー Diana773
提出日時 2024-03-08 23:02:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,024 bytes
コンパイル時間 1,854 ms
コンパイル使用メモリ 171,596 KB
実行使用メモリ 7,516 KB
最終ジャッジ日時 2024-09-29 20:32:18
合計ジャッジ時間 5,505 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

pair<int,int> a[200010];
pair<int,int> b[200010];
int p[200010];
int _;
int n,l,r,m,tt,ll,rr;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i].first>>a[i].second;
		b[i].first=-a[i].second;
		b[i].second=-a[i].first;
	}
	sort(a+1,a+1+n);
	for (int i=1; i<=n; i++)
	{
		p[i]=max(p[i-1]+1,a[i].first);
	    //cout<<i<<" "<<p[i]<<endl;
	    //cout<<i<<" "<<a[i].first<<" "<<a[i].second<<endl;
	}
	for (int i=n-1; i>=1; i--)
	{
		p[i]=p[i+1]-1;
	}
	
	ll=p[1];
	int fl=1;
	for (int i=1; i<=n; i++)
	{
		if (!(p[i]>=a[i].first && p[i]<=a[i].second))
		  fl=0;
	}
	if (fl==0)
	{
		cout<<0;
		return 0;
	}
	
	sort(b+1,b+1+n);
	for (int i=1; i<=n; i++)
	{
		a[i].first=-b[i].second;
		a[i].second=-b[i].first;
		//cout<<i<<" "<<a[i].first<<" "<<a[i].second<<endl;
	}
	p[0]=2000000000;
	for (int i=1; i<=n; i++)
	{
		p[i]=min(p[i-1]-1,a[i].second);
		//cout<<i<<" "<<p[i]<<endl;
	}
	rr=p[n];
	
	cout<<rr-ll+1<<'\n';
	
	return 0;
}
0