Submission #1224010

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=101000;
struct node {
	int fg,mv;
}nd[4*N];
multiset<PII> ff[4*N];
int n,a[N],b[N],c[N],Q,p,q,f[N],pre[N];
VI pos[N];
void upd(int p) { nd[p].mv=max(nd[p+p].mv,nd[p+p+1].mv);}
void setf(int p,int v) {
	nd[p].fg+=v;
	nd[p].mv+=v;
}
void build(int p,int l,int r) {
	nd[p].fg=0;
	if (l==r) {
		nd[p].mv=pre[l];
	} else {
		int md=(l+r)>>1;
		build(p+p,l,md);
		build(p+p+1,md+1,r);
		upd(p);
	}
}
void push(int p) {
	if (nd[p].fg) {
		setf(p+p,nd[p].fg);
		setf(p+p+1,nd[p].fg);
		nd[p].fg=0;
	}
}
int query(int p,int l,int r,int tl,int tr) {
	if (tl==l&&tr==r) return nd[p].mv;
	else {
		push(p);
		int md=(l+r)>>1;
		if (tr<=md) return query(p+p,l,md,tl,tr);
		else if (tl>md) return query(p+p+1,md+1,r,tl,tr);
		else return max(query(p+p,l,md,tl,md),query(p+p+1,md+1,r,md+1,tr));
	}
}
void modify(int p,int l,int r,int tl,int tr,int v) {
	if (tl>tr) return;
	if (tl==l&&tr==r) return setf(p,v);
	else {
		push(p);
		int md=(l+r)>>1;
		if (tr<=md) modify(p+p,l,md,tl,tr,v);
		else if (tl>md) modify(p+p+1,md+1,r,tl,tr,v);
		else modify(p+p,l,md,tl,md,v),modify(p+p+1,md+1,r,md+1,tr,v);
		upd(p);
	}
}
void add(int p,int l,int r,int tl,int tr,PII v) {
	if (tl>tr) return;
	if (tl==l&&tr==r) ff[p].insert(v);
	else {
		int md=(l+r)>>1;
		if (tr<=md) add(p+p,l,md,tl,tr,v);
		else if (tl>md) add(p+p+1,md+1,r,tl,tr,v);
		else add(p+p,l,md,tl,md,v),add(p+p+1,md+1,r,md+1,tr,v);
	}
}

void del(int p,int l,int r,int tl,int tr,PII v) {
	if (tl>tr) return;
	if (tl==l&&tr==r) ff[p].erase(ff[p].find(v));
	else {
		int md=(l+r)>>1;
		if (tr<=md) del(p+p,l,md,tl,tr,v);
		else if (tl>md) del(p+p+1,md+1,r,tl,tr,v);
		else del(p+p,l,md,tl,md,v),del(p+p+1,md+1,r,md+1,tr,v);
	}
}

PII find(int p,int l,int r,int x) {
	PII c=mp(-1,-1);
	if (!ff[p].empty()) c=max(c,*ff[p].rbegin());
	if (l!=r) {
		int md=(l+r)>>1;
		if (x<=md) c=max(c,find(p+p,l,md,x));
		else c=max(c,find(p+p+1,md+1,r,x));
	}
	return c;
}
multiset<PII> Bl;
vector<PII> blk[N];

int main() {
	scanf("%d",&n);
	rep(i,0,n) scanf("%d%d",a+i,b+i);
	rep(i,0,n+1) scanf("%d",c+i);
	sort(c,c+n+1);
	pre[0]-=1;
	f[0]=0;
	rep(i,0,n) {
		a[i]=lower_bound(c,c+n+1,a[i])-c;
		b[i]=lower_bound(c,c+n+1,b[i])-c;
//		printf("pp %d %d\n",a[i],b[i]);
		if (a[i]<=b[i]) f[0]++,pre[a[i]]-=1;
		else {
			// a[i]>b[i]
			pos[a[i]].pb(b[i]);
			pre[b[i]]-=1;
		}
	}
	rep(i,0,n+1) pre[i]++;
	rep(i,1,n+1) pre[i]+=pre[i-1];
	build(1,0,n);
	rep(i,1,n+2) f[i]=-(1<<30);
	if (nd[1].mv<=0) {
		rep(r,0,n+1) {
			sort(all(pos[r]));
			for (auto l:pos[r]) {
				if (l<r&&query(1,0,n,l,r-1)<0) {
					modify(1,0,n,l,r-1,1),add(1,0,n,l,r-1,mp(r-1,l)),f[0]++;
//					printf("set %d %d\n",l,r-1);
				} else if (l<r) {
					blk[l].pb(mp(r-1,l));
				}
			}
		}
		Bl.clear();
		rep(i,1,n+1) for (auto p:blk[i]) Bl.insert(p);

//		printf("ff %d %d\n",0,f[0]);
		rep(i,1,n+1) {
			if (query(1,0,n,i-1,i-1)<0) {
				f[i]=f[i-1];
				modify(1,0,n,i-1,i-1,1);
			} else {
				PII c=find(1,0,n,i-1);
				if (c==mp(-1,-1)) break;
//				printf("cancel %d %d\n",c.fi,c.se);
				f[i]=f[i-1]-1;
				modify(1,0,n,c.se,c.fi,-1);
				modify(1,0,n,i-1,i-1,1);
				del(1,0,n,c.se,c.fi,c);
				if (!Bl.empty()) {
					PII d=*Bl.begin();
//					printf("rr %d %d\n",d.fi,d.se);
					if (query(1,0,n,d.se,d.fi)<0) {
						modify(1,0,n,d.se,d.fi,1);
						add(1,0,n,d.se,d.fi,d);
//						printf("replace %d %d\n",d.fi,d.se);
						f[i]++;
						Bl.erase(Bl.begin());
					}
				}
			}
//			printf("ff %d %d\n",i,f[i]);
			for (auto p:blk[i]) if (Bl.find(p)!=Bl.end()) Bl.erase(Bl.find(p));
		}

	} else f[0]=-(1<<30);
	scanf("%d",&Q);
	rep(i,0,Q) {
		scanf("%d%d",&p,&q);
		p=lower_bound(c,c+n+1,p)-c,q=lower_bound(c,c+n+1,q)-c;
//		printf("q %d %d\n",p,q);
		int r=max(max(f[p]+1,f[q]),-1);
		printf("%d\n",r);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:114:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:115:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,0,n) scanf("%d%d",a+i,b+i);
                                  ^
./Main.cpp:116:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,0,n+1) scanf("%d",c+i);
                              ^
./Main.cpp:180:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
./Main.cpp:182:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,&q);
                      ^

Judge Result