Submission #1773162

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define SZ 666666
int n; typedef pair<int,int> pii;
pii ps[SZ],gs[SZ];
#define fi first
#define se second
typedef long long ll;
const ll MOD=1e9+7;
ll tag[SZ]; //mul
int ls[SZ],rs[SZ];
const int M=262144;
bool by_2(pii x,pii y)
{
	swap(x.fi,x.se);
	swap(y.fi,y.se);
	return x<y;
}
void init()
{
	for(int i=1;i<=M;i++) ls[i+M]=rs[i+M]=i-1;
	for(int i=M-1;i>=1;--i)
		ls[i]=ls[i+i],rs[i]=rs[i+i+1];
	for(int i=1;i<=M+M;++i) tag[i]=1;
}
ll sum[SZ];
void pd(int x)
{
	if(tag[x]!=1)
	{
		sum[x]=sum[x]*tag[x]%MOD;
		if(x<=M)
			tag[x+x]=tag[x+x]*tag[x]%MOD,
			tag[x+x+1]=tag[x+x+1]*tag[x]%MOD;
		tag[x]=1;
	}
}
void upd(int x)
{
	pd(x+x); pd(x+x+1);
	sum[x]=(sum[x+x]+sum[x+x+1])%MOD;
}
ll qsum(int x,int l,int r)
{
	if(rs[x]<l||r<ls[x]||l>r) return 0;
	pd(x); if(l<=ls[x]&&rs[x]<=r) return sum[x];
	ll ans=(qsum(x+x,l,r)+qsum(x+x+1,l,r))%MOD;
	upd(x); return ans;
}
void addt(int x,int l,int r,ll t)
{
	if(rs[x]<l||r<ls[x]||l>r) return;
	pd(x); if(l<=ls[x]&&rs[x]<=r)
	{tag[x]=tag[x]*t%MOD; return;}
	addt(x+x,l,r,t); addt(x+x+1,l,r,t); upd(x);
}
void adds(int x,int l,ll g)
{
	if(rs[x]<l||l<ls[x]) return;
	pd(x); if(ls[x]==rs[x]&&ls[x]==l)
	{sum[x]=(sum[x]+g)%MOD; return;}
	adds(x+x,l,g); adds(x+x+1,l,g); upd(x);
}
#define tm tmd
int r[SZ],l[SZ],tm[SZ],t[SZ];
int bs[SZ];
int qmax(int x)
{
	int ans=-1e9;
	for(;x>=1;x-=x&-x) ans=max(ans,bs[x]);
	return ans;
}
void edt(int x,int y)
{
	for(;x<=n;x+=x&-x) bs[x]=max(bs[x],y);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&ps[i].fi,&ps[i].se),tm[i]=ps[i].fi;
	sort(ps+1,ps+1+n,by_2); sort(tm+1,tm+1+n);
	for(int i=1;i<=n;i++) t[i]=lower_bound(tm+1,tm+1+n,ps[i].fi)-tm;
	memset(bs,-127/3,sizeof bs);
	for(int i=1;i<=n;i++)
		edt(n+1-t[i],-i), l[i]=-qmax(n+1-t[i]);
	memset(bs,-127/3,sizeof bs);
	for(int i=n;i>=1;--i)
		edt(t[i],i), r[i]=qmax(t[i]);
	for(int i=1;i<=n;i++) gs[i]=pii(l[i],r[i]);
	sort(gs+1,gs+1+n); init(); adds(1,0,1);
	for(int i=1;i<=n;i++)
	{
		int l=gs[i].fi,r=gs[i].se;
		ll tmp=qsum(1,l-1,r); adds(1,r,tmp); addt(1,r+1,n,2);
	}
	ll aa=qsum(1,n,n);
	aa=(aa%MOD+MOD)%MOD;
	printf("%d\n",int(aa));
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:81:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&ps[i].fi,&ps[i].se),tm[i]=ps[i].fi;
                                                   ^

Judge Result