Submission #1228255

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <string>
#include <cassert>
#define SIZE 200005
#define BT 256*1024*2
#define INF 1000000005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct segtree2
{
	int seg[BT];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++) seg[i]=-1;
	}
	void update(int a,int b,int k,int l,int r,int v)
	{
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b) seg[k]=max(seg[k],v);
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
		}
	}
	void update(int a,int b,int v)
	{
		update(a,b,0,0,mum,v);
	}
	int get(int k)
	{
		k+=mum-1;
		int ret=seg[k];
		while(k>0)
		{
			k=(k-1)/2;
			ret=max(ret,seg[k]);
		}
		return ret;
	}
};
struct segtree//区間可算+区間min
{
	int seg[BT],add[BT];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++) seg[i]=add[i]=0;
	}
	void update(int a,int b,int k,int l,int r,int v)
	{
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b)
		{
			seg[k]+=v;
			add[k]+=v;
		}
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,v);
			update(a,b,k*2+2,(l+r)/2,r,v);
			seg[k]=min(seg[k*2+1],seg[k*2+2])+add[k];
		}
	}
	void update(int a,int b,int v)
	{
		update(a,b,0,0,mum,v);
	}
	int get(int a,int b,int k,int l,int r)
	{
		if(b<=l||r<=a) return INF;
		if(a<=l&&r<=b) return seg[k];
		else
		{
			int vl=get(a,b,k*2+1,l,(l+r)/2);
			int vr=get(a,b,k*2+2,(l+r)/2,r);
			return min(vl,vr)+add[k];
		}
	}
	int get(int a,int b)
	{
		return get(a,b,0,0,mum);
	}
};
segtree seg;
segtree2 s2;
int A[SIZE],B[SIZE],C[SIZE];
int M[SIZE];//M[i]=min(A[i],B[i]);
int ans[SIZE],dp[SIZE];
int mx[SIZE];
int nxt[SIZE];
bool ok[SIZE];
vector <int> vx;
int n;

void build()
{
	seg.init(vx.size()+2);
	for(int i=0;i<=n;i++) seg.update(0,C[i]+1,1);
	for(int i=0;i<n;i++) seg.update(0,M[i]+1,-1);
	if(seg.get(0,vx.size()+1)<0)
	{
		for(int i=0;i<vx.size();i++) ans[i]=-1;
		return;
	}
	vector <P> query;
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(M[i]<A[i]) query.push_back(P(A[i],M[i]+1));
		else cnt++;
	}
	vector <P> zan;
	sort(query.begin(),query.end());
	s2.init(vx.size()+2);
	for(int i=0;i<query.size();i++)
	{
		P p=query[i];
		if(seg.get(p.second,p.first+1)<=0) zan.push_back(P(p.second,p.first));
		else
		{
			s2.update(p.second,p.first+1,p.first);
			seg.update(p.second,p.first+1,-1);
			cnt++;
		}
	}
	for(int i=0;i<vx.size();i++) mx[i]=s2.get(i);
	nxt[vx.size()]=vx.size();
	for(int i=vx.size()-1;i>=0;i--)
	{
		nxt[i]=nxt[i+1];
		if(seg.get(i,i+1)==0) nxt[i]=i;
	}
	sort(zan.begin(),zan.end());
	int to=((int) zan.size())-1;
	int mn=INF;
	dp[vx.size()]=INF;
	for(int i=vx.size()-1;i>=0;i--)
	{
		//i～dp[i] まで +1 したとき、個数も+1できるかどうかの最小のdp[i]を求めたい
		while(to>=0&&zan[to].first>=i)
		{
			mn=min(mn,zan[to].second);
			to--;
		}
		if(to+1==zan.size())
		{
			dp[i]=INF;
			continue;
		}
		int l=i-1,r=mn;//mnならokは確実
		while(r-l>1)
		{
			int m=(l+r)/2;//m+1<=mn
			if(nxt[m+1]>mn) r=m;
			else
			{
				int t=nxt[m+1];
				if(mx[t]>mn&&dp[mn+1]<=mx[t]) r=m;
				else l=m;
			}
		}
		dp[i]=r;
	}
	//for(int i=0;i<vx.size();i++) printf("%d ",dp[i]);puts("");
	//for(int i=0;i<vx.size();i++) printf("%d ",seg.get(i,i+1));puts("");
	//for(int i=0;i<vx.size();i++) printf("%d ",mx[i]);puts("");
	for(int i=0;i<vx.size();i++)
	{
		if(nxt[i]!=i) ans[i]=cnt;
		else
		{
			int t=mx[i];
			if(t==-1)
			{
				for(int j=i;j<vx.size();j++) ans[j]=-1;
				break;
			}
			for(int j=i;j<=t;j++)
			{
				if(nxt[j]!=j) ans[j]=ans[j-1];
				else
				{
					if(dp[j+1]<=t) ans[j]=cnt;
					else ans[j]=cnt-1;
				}
			}
			cnt--;
			i=t;
		}
	}
	//for(int i=0;i<=n;i++) printf("%d ",ans[i]);puts("");
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&A[i],&B[i]);
		M[i]=min(A[i],B[i]);
	}
	vx.push_back(INF);
	for(int i=0;i<=n;i++)
	{
		scanf("%d",&C[i]);
		vx.push_back(C[i]);
	}
	sort(C,C+n+1);
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	for(int i=0;i<n;i++)
	{
		A[i]=lower_bound(vx.begin(),vx.end(),A[i])-vx.begin();
		M[i]=lower_bound(vx.begin(),vx.end(),M[i])-vx.begin();
	}
	for(int i=0;i<=n;i++) C[i]=lower_bound(vx.begin(),vx.end(),C[i])-vx.begin();
	build();
	int Q;
	scanf("%d",&Q);
	for(int i=0;i<Q;i++)
	{
		int d,e;
		scanf("%d %d",&d,&e);
		int ret=-1;
		//d使う場合
		int pos=lower_bound(vx.begin(),vx.end(),d)-vx.begin();
		int pc=lower_bound(C,C+n+1,pos)-C;
		if(pc<=n&&ans[C[pc]]!=-1) ret=max(ret,ans[C[pc]]+1);
		//e使う場合
		pos=lower_bound(vx.begin(),vx.end(),e)-vx.begin();
		pc=lower_bound(C,C+n+1,pos)-C;
		if(pc<=n&&ans[C[pc]]!=-1) ret=max(ret,ans[C[pc]]);
		printf("%d\n",ret);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:215:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:218:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&A[i],&B[i]);
                             ^
./Main.cpp:224:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&C[i]);
                    ^
./Main.cpp:238:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
./Main.cpp:242:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&d,&e);
                       ^

Judge Result