Submission #1587053


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 21376 KB
04.txt TLE 2104 ms 23424 KB
05.txt RE 245 ms 21376 KB
06.txt RE 299 ms 21376 KB
07.txt TLE 2104 ms 21376 KB
08.txt TLE 2104 ms 21376 KB
09.txt WA 233 ms 21888 KB
10.txt RE 220 ms 21376 KB
11.txt WA 176 ms 21888 KB
12.txt WA 231 ms 21888 KB
13.txt WA 165 ms 21888 KB
14.txt WA 177 ms 21888 KB
15.txt WA 232 ms 21888 KB
16.txt WA 165 ms 21888 KB
17.txt WA 164 ms 21888 KB
18.txt WA 234 ms 21888 KB
19.txt WA 165 ms 21888 KB
20.txt WA 165 ms 21888 KB
21.txt WA 251 ms 21888 KB
22.txt WA 186 ms 21888 KB
23.txt WA 186 ms 21888 KB
24.txt WA 249 ms 21888 KB
25.txt TLE 2104 ms 21376 KB
26.txt TLE 2104 ms 21376 KB
27.txt TLE 2104 ms 23424 KB
28.txt TLE 2104 ms 21376 KB
29.txt TLE 2104 ms 21376 KB
30.txt WA 1984 ms 21888 KB
31.txt AC 3 ms 10496 KB
32.txt AC 3 ms 10496 KB
33.txt AC 2 ms 10496 KB
34.txt WA 2 ms 10496 KB
s1.txt AC 2 ms 10496 KB
s2.txt AC 2 ms 10496 KB