Submission #3765384

---

Source Code Expand

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1005000000
#define MOD 1000000007
#define N 200005
#define M 1000005
#define LOG 19
#define KOK 32000
#define EPS 0.000000001
using namespace std;

int n,x,y,ans,v;
int s[N*4],dp[N],pre[N];
vector<ii> ar;

int get(int node,int bas,int son,int x,int y) {

	if(bas>=x && son<=y) return s[node];

	if(bas>y || son<x) return inf;

	return min(get(node<<1,bas,orta,x,y),get(node<<1|1,orta+1,son,x,y));

}

void up(int node,int bas,int son,int x,int val) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		umin(s[node],val);

		return;

	}

	up(node<<1,bas,orta,x,val);
	up(node<<1|1,orta+1,son,x,val);

	s[node]=min(s[node<<1],s[node<<1|1]);

}

void build(int node,int bas,int son,int val) {

	if(bas==son) {

		s[node]=val;

		return ;

	}

	build(node<<1,bas,orta,val);
	build(node<<1|1,orta+1,son,val);

	s[node]=min(s[node<<1],s[node<<1|1]);

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d",&n);

	vector<ii> range(n+1);

	for(int i=1;i<=n;i++) {

		scanf("%d %d",&x,&v);

		ar.pb({x,v});

	}

	sort(all(ar));

	int cnt=0;

	for(int i=0;i<n;i++) {

		++cnt;

		while(i+1<n && ar[i].st==ar[i+1].st) {

			swap(ar[i].st,ar[i].nd);

			ar[i].nd=cnt;

			i++;

		}
		
		swap(ar[i].st,ar[i].nd);

		ar[i].nd=cnt;

	}

	sort(all(ar));

	build(1,1,cnt,inf);

	for(int i=0;i<n;i++) {

		up(1,1,n,ar[i].nd,i+1);

		range[i+1].st=get(1,1,cnt,ar[i].nd,cnt);

	}

	build(1,1,cnt,inf);

	for(int i=n-1;i>=0;i--) {

		up(1,1,n,ar[i].nd,-i-1);

		range[i+1].nd=-get(1,1,cnt,1,ar[i].nd);

	}

	range[0]={-inf,0};

	sort(all(range),[](ii a,ii b) {

		if(a.nd==b.nd) return a.st<b.st;

		return a.nd<b.nd;

	});

	dp[0]=pre[0]=1;

	for(int i=1;i<=n;i++) {

		int bas=0,son=i-1;

		while(bas<=son) {

			if(range[orta].nd<range[i].st-1) bas=orta+1;
			else son=orta-1;

		}

		dp[i]=(pre[i-1]-(son<0?0:pre[son])+MOD)%MOD;

		pre[i]=(pre[i-1]+dp[i])%MOD;

	}

	for(int i=n;i>=1;i--) {

		if(range[i].nd<n) break ;

		ans=(ans+dp[i])%MOD;

	}

	printf("%d",ans);

}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:88:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&v);
                       ^

Judge Result