Submission #2141533

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<int>za;
int dp[500005];
int n,q,a[100005],b[100005],c[100005],d[100005],e[100005];
int len[500005],num[500005],gen[500005];
struct segtree{
	int seg[(1<<20)];
	void allinit(){
	    memset(seg,0,sizeof(seg));
	}
	void init(int pos,int val){
		seg[pos+(1<<19)-1] = val;
	}
	void update(int a,int b,int k,int l,int r,int val){
		if(r<a||b<l) return;
		if(a<=l&&r<=b){
			seg[k]+=val;
			return;
		}
		update(a,b,k*2+1,l,(l+r)/2,val);
		update(a,b,k*2+2,(l+r)/2+1,r,val);
	}
	int query(int a,int k,int l,int r){
		if(l==r) return seg[k];
		if(l<=a&&a<=(l+r)/2){
			return seg[k]+query(a,k*2+1,l,(l+r)/2);
		}
		else{
			return seg[k]+query(a,k*2+2,(l+r)/2+1,r);
		}
	}
}seg;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		za.pb(a[i]); za.pb(b[i]);
	}
	for(int i=1;i<=n+1;i++){
		scanf("%d",&c[i]);
		za.pb(c[i]);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&d[i],&e[i]);
		za.pb(d[i]); za.pb(e[i]);
	}
	sort(c+1,c+n+2);
	za.pb(-1);
	SORT(za); ERASE(za);
	for(int i=1;i<=n+1;i++){
		c[i] = POSL(za,c[i]);
		num[c[i]] = i;
	}
	vector<P>interval;
	for(int i=1;i<=n;i++){
		a[i] = POSL(za,a[i]);
		b[i] = POSL(za,b[i]);
		gen[a[i]]++;
		if(a[i] > b[i]){
			interval.pb(mp(b[i],a[i]-1));
		}
	}
	for(int i=2;i<za.size();i++) gen[i] += gen[i-1];
	for(int i=1;i<za.size();i++){
		num[i] -= gen[i];
		seg.init(i,num[i]);
	}
	SORT(interval); int nxt = 0;
	rep(i,500005) len[i] = dp[i] = INF;
	priority_queue<int>que;
	int fail = -1;
	for(int i=1;i<za.size();i++){
		while(nxt<interval.size() && interval[nxt].fi == i){
			que.push(interval[nxt].sc);
			nxt++;
		}
		if(seg.query(i,0,0,(1<<19)-1) <= 0) continue;
		while(seg.query(i,0,0,(1<<19)-1) > 0){
			if(que.empty() || que.top()<i){
				fail = i;
				break;
			}
			len[i] = que.top();
			que.pop();
			seg.update(i,len[i],0,0,(1<<19)-1,-1);
		}
		if(fail != -1) break;
	}
	//calc dp[fail]
	seg.allinit();
	for(int i=1;i<za.size();i++){
		seg.init(i,num[i]);
	}
	nxt = 0;
	while(que.size()) que.pop();
	int sum = 0;
	for(int i=1;i<za.size();i++){
		while(nxt<interval.size() && interval[nxt].fi == i){
			que.push(interval[nxt].sc);
			nxt++;
		}
		if(i == fail){
			que.push(za.size()-1);
		}
		if(seg.query(i,0,0,(1<<19)-1) <= 0) continue;
		while(seg.query(i,0,0,(1<<19)-1) > 0){
			if(que.empty() || que.top()<i){
				sum = INF;
				break;
			}
			int x = que.top();
			que.pop();
			seg.update(i,x,0,0,(1<<19)-1,-1);
			sum++;
		}
		if(sum == INF) break;
	}
	if(sum == INF) dp[fail] = INF;
	else{
		dp[fail] = sum-1;
	}
	for(int i=fail-1;i>=1;i--){
		if(len[i] == INF){
			dp[i] = min(dp[i],dp[i+1]);
		}
		else{
			dp[i] = min(dp[i],min(dp[i+1],dp[len[i]+1]-1));
		}
	}
	for(int i=1;i<=q;i++){
		d[i] = POSL(za,d[i]); e[i] = POSL(za,e[i]);
		int sub = min(dp[d[i]],dp[e[i]]+1);
		if(sub<=1e7) printf("%d\n",n+1-sub);
		else puts("-1");
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:54:28: 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:58:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c[i]);
                    ^
./Main.cpp:61:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
./Main.cpp:63:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&d[i],&e[i]);
                            ^

Judge Result