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 |
× 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 |