Submission #1587052


Source Code Expand

#include <bits/stdc++.h>
#define mod 1000000007
#define N 400010
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
inline void pls(int &x,int y)
{
	x+=y; if(x>=mod) x-=mod;
	if(x<0) x+=mod; 
}
int n,L[N],R[N],tree[N<<1];
inline void deal(int x,int y,int tp)
{
	//if(tp==0) cerr << x << " " << y << " " << tp << endl;
	if(tp==1&&tree[x]==0) tree[x]=0x3ffffff;
	if(tp==0) pls(tree[x],y);
	if(tp==1) tree[x]=min(tree[x],y);
	if(tp==2) tree[x]=max(tree[x],y);
	//if(tp==0) cout << tree[x] << endl;
}
inline void qury(int &x,int y,int tp)
{
	if(tp==1&&x==0) x=0x3ffffff;
	if(tp==0) pls(x,y);
	if(tp==1) x=min(x,y);
	if(tp==2) x=max(x,y);
}
inline void add(int x,int y,int tp)
{
	//cout << x << " " << y << " " << tp << " "  << endl;
	for(;x<=n;x+=(x&-x))
		deal(x,y,tp);
}
inline int ask(int x,int tp)
{
	int ret=0; for(;x;x-=(x&-x))
		qury(ret,tree[x],tp); return ret;
}
pair <int,int> Ps[N]; map <int,int> M;
int V[N],Fs[N],rk[N];
inline bool cmp(const int a,const int b)
{
	return (L[a]==L[b])? R[a]<=R[b]:L[a]<L[b];
}
int main()
{
	n=read(); 
	for(int i=1;i<=n;i++)
		Ps[i].second=read(), Ps[i].first=read(),V[++V[0]]=Ps[i].second;
	sort(V+1,V+1+V[0]);
	for(int i=1;i<=V[0];i++) M[V[i]]=i;
	for(int i=1;i<=V[0];i++) Ps[i].second=M[Ps[i].second];
	sort(Ps+1,Ps+1+n);
	for(int i=1;i<=n;i++)
		add(n-Ps[i].second+1,i,1),L[i]=max(1,ask(n-Ps[i].second+1,1));
	memset(tree,0,sizeof tree);
	for(int i=n;i>=1;i--)
		add(Ps[i].second,i,2),R[i]=min(n,ask(Ps[i].second,2));
	memset(tree,0,sizeof tree);
	
	for(int i=1;i<=n;i++) rk[i]=i;
	//for(int i=1;i<=n;i++) printf("%d %d\n",L[rk[i]],R[rk[i]]);
	sort(rk+1,rk+1+n,cmp);
	//for(int i=1;i<=n;i++) printf("%d %d\n",L[rk[i]],R[rk[i]]);
	int ans=0;
	for(int i=n;i>=1;i--)
	{
		if(R[rk[i]]==n) Fs[i]=1;
		Fs[i]+=ask(R[rk[i]],0);
		if(L[rk[i]]==1) pls(ans,Fs[i]);
		add(L[rk[i]],Fs[i],0);
		//cout << Fs[i] << " ";
	}
	//cout <<endl;
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Mr.Aoki Incubator
User wcz111
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2156 Byte
Status RE
Exec Time 2104 ms
Memory 23424 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1200
Status
AC × 2
AC × 5
WA × 17
TLE × 11
RE × 3
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt TLE 2104 ms 21376 KB
02.txt TLE 2104 ms 21376 KB
03.txt TLE 2104 ms 23424 KB
04.txt TLE 2104 ms 21376 KB
05.txt RE 244 ms 21376 KB
06.txt RE 300 ms 21376 KB
07.txt TLE 2104 ms 21376 KB
08.txt TLE 2104 ms 21376 KB
09.txt WA 244 ms 21888 KB
10.txt RE 222 ms 21376 KB
11.txt WA 178 ms 21888 KB
12.txt WA 234 ms 21888 KB
13.txt WA 170 ms 21888 KB
14.txt WA 179 ms 21888 KB
15.txt WA 238 ms 21888 KB
16.txt WA 171 ms 21888 KB
17.txt WA 164 ms 21888 KB
18.txt WA 251 ms 21888 KB
19.txt WA 167 ms 21888 KB
20.txt WA 168 ms 21888 KB
21.txt WA 249 ms 21888 KB
22.txt WA 185 ms 21888 KB
23.txt WA 188 ms 21888 KB
24.txt WA 260 ms 21888 KB
25.txt TLE 2104 ms 21376 KB
26.txt TLE 2104 ms 23424 KB
27.txt TLE 2104 ms 21376 KB
28.txt TLE 2104 ms 21376 KB
29.txt TLE 2104 ms 21376 KB
30.txt WA 1989 ms 21888 KB
31.txt AC 3 ms 10496 KB
32.txt AC 4 ms 10496 KB
33.txt AC 3 ms 10496 KB
34.txt WA 3 ms 10496 KB
s1.txt AC 3 ms 10496 KB
s2.txt AC 3 ms 10496 KB