Submission #1712573

---

Source Code Expand

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;

const int maxn = 210000;

int n,m;
int A[maxn],B[maxn],C[maxn];

struct node{int x,i;};
inline bool operator <(const node x,const node y){return x.x<y.x;}
set<node>S;
set<node>::iterator it;

int p[maxn],q[maxn];
struct L{int l,i;};
vector<L>vl[maxn];
inline bool operator <(const L x,const L y){return x.l>y.l;}
priority_queue<L>q1;
struct R{int r,i;};
vector<R>vr[maxn];
inline bool operator <(const R x,const R y){return x.r<y.r;}
priority_queue<R>q2;

bool use[maxn],flag;
int ans[maxn],re;

int solve(const int k,const int ad){ return ans[k]==-1?-1:n-ans[k]+ad; }

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]);
	for(int i=0;i<=n;i++) scanf("%d",&C[i]); sort(C,C+n+1);
	for(int i=0;i<=n;i++) if(!i||C[i]!=C[i-1]) S.insert((node){C[i],i});
	S.insert((node){inf+1,n+1});
	
	for(int i=1;i<=n;i++)
	{
		it=S.lower_bound((node){A[i],0});
		A[i]=(*it).i; p[A[i]]++;
		it=S.lower_bound((node){B[i],0});
		B[i]=(*it).i;
		
		if(A[i]>B[i])
		{
			swap(A[i],B[i]); B[i]--;
			vl[B[i]].push_back((L){A[i],i});
			vr[A[i]].push_back((R){B[i],i});
		}
	}
	for(int i=0;i<=n;i++) p[i]--;
	for(int i=1;i<=n+1;i++) p[i]+=p[i-1];
	
	int ad=0;
	for(int i=n+1;i>=0;i--)
	{
		ad+=q[i]; p[i]+=ad; q[i]=0;
		for(int j=0;j<vl[i].size();j++) q1.push(vl[i][j]);
		
		if(p[i]<-1&&i!=n+1)
		{
			while(!q1.empty()&&p[i]<-1)
			{
				const L now=q1.top(); q1.pop();
				if(now.l>i) break;
				use[now.i]=true;
				p[i]++; ad++; if(now.l) q[now.l-1]--;
				if(B[now.i]>i) q[i+1]++,q[B[now.i]+1]--;
				re++;
			}
			if(p[i]<-1) { flag=true; break; }
		}
	}
	if(flag) for(int i=0;i<=n+1;i++) ans[i]=-1;
	else
	{
		ad=0;
		for(int i=0;i<=n;i++) ad+=q[i],q[i]=0,p[i]+=ad;
		ad=0;
		for(int i=0;i<=n;i++)
		{
			ans[i]=re;
			ad+=q[i]; p[i]+=ad;
			for(int j=0;j<vr[i].size();j++) if(!use[vr[i][j].i]) q2.push(vr[i][j]);
			
			if(p[i]<0)
			{
				while(!q2.empty()&&p[i]<0)
				{
					const R now=q2.top(); q2.pop();
					if(now.r<i) break;
					ad++; p[i]++; q[now.r+1]--;
					re++;
				}
				if(p[i]<0)
				{
					for(int j=i+1;j<=n+1;j++) ans[j]=-1;
					break;
				}
			}
		}
		if(ans[n+1]!=-1) ans[n+1]=re;
	}
	
	scanf("%d",&m);
	while(m--)
	{
		int x,y; scanf("%d%d",&x,&y);
		it=S.lower_bound((node){x,0}); x=(*it).i;
		it=S.lower_bound((node){y,0}); y=(*it).i;
		printf("%d\n",max(solve(x,1),solve(y,0)));
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:50:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d",&A[i],&B[i]);
                                                 ^
./Main.cpp:51:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<=n;i++) scanf("%d",&C[i]); sort(C,C+n+1);
                                         ^
./Main.cpp:123:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
./Main.cpp:126:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-W...

Judge Result