Submission #2697202
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
inline char nchar() {
static const int bufl=1<<20;
static char buf[bufl],*a=NULL,*b=NULL;
return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;
}
inline int read() {
int x=0,f=1;
char c=nchar();
for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;
for (;isdigit(c);c=nchar()) x=x*10+c-'0';
return x*f;
}
template<typename T> inline T& Min(T &x,const T &y) {return x>y?(x=y):x;}
template<typename T> inline T& Max(T &x,const T &y) {return x<y?(x=y):x;}
const int q=1e9+7;
inline int Plus(int x,int y) {return x+y>=q?(x+y-q):(x+y);}
inline int Sub(int x,int y) {return x<y?(x-y+q):(x-y);}
inline int& Pe(int &x,int y) {return x=Plus(x,y);}
const int maxn=2e5+10;
int n,L[maxn],R[maxn];
struct A {
int x,v;
inline bool operator < (const A &d) const {
return x<d.x;
}
} a[maxn];
struct range {
int l,r;
inline bool operator < (const range &d) const {
return r<d.r;
}
} b[maxn];
void disc() {
static int V[maxn];
for (int i=1;i<=n;++i) V[i]=a[i].v;
sort(V+1,V+n+1);
for (int i=1;i<=n;++i) a[i].v=lower_bound(V+1,V+n+1,a[i].v)-V;
}
namespace bit {
int n,c[maxn];
inline void set_n(int _n) {
n=_n+1;
}
inline int lowbit(int x) {
return x&-x;
}
void inc(int x,int d) {
for (++x;x<=n;x+=lowbit(x)) Pe(c[x],d);
}
int sum(int x) {
int ret(0);
for (++x;x;x-=lowbit(x)) Pe(ret,c[x]);
return ret;
}
inline int sum(int x,int y) {
return sum(y)-sum(x-1);
}
}
int main() {
n=read();
for (int i=1;i<=n;++i) a[i].x=read(),a[i].v=read();
disc();
sort(a+1,a+n+1);
for (int i=1,tmp=INT_MIN;i<=n;++i) b[i].r=Max(tmp,a[i].v);
for (int i=n,tmp=INT_MAX;i>0;--i) b[i].l=Min(tmp,a[i].v);
sort(b+1,b+n+1);
bit::set_n(n);
bit::inc(0,1);
for (int i=1;i<=n;++i) {
int tmp=bit::sum(b[i].l-1,b[i].r);
bit::inc(b[i].r,tmp);
}
int ans=bit::sum(n,n);
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Mr.Aoki Incubator |
User |
permui |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1940 Byte |
Status |
WA |
Exec Time |
72 ms |
Memory |
7552 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1200 |
Status |
|
|
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 |
WA |
53 ms |
6784 KB |
02.txt |
WA |
54 ms |
6784 KB |
03.txt |
WA |
64 ms |
6784 KB |
04.txt |
WA |
53 ms |
6784 KB |
05.txt |
WA |
53 ms |
6912 KB |
06.txt |
WA |
64 ms |
6784 KB |
07.txt |
WA |
53 ms |
6784 KB |
08.txt |
WA |
53 ms |
6784 KB |
09.txt |
AC |
70 ms |
7552 KB |
10.txt |
AC |
31 ms |
6784 KB |
11.txt |
WA |
37 ms |
7552 KB |
12.txt |
WA |
70 ms |
7552 KB |
13.txt |
WA |
36 ms |
7552 KB |
14.txt |
WA |
37 ms |
7552 KB |
15.txt |
WA |
70 ms |
7552 KB |
16.txt |
WA |
36 ms |
7552 KB |
17.txt |
WA |
37 ms |
7552 KB |
18.txt |
WA |
70 ms |
7552 KB |
19.txt |
WA |
35 ms |
7552 KB |
20.txt |
WA |
37 ms |
7552 KB |
21.txt |
WA |
72 ms |
7552 KB |
22.txt |
WA |
40 ms |
7552 KB |
23.txt |
WA |
40 ms |
7552 KB |
24.txt |
WA |
71 ms |
7552 KB |
25.txt |
WA |
37 ms |
6912 KB |
26.txt |
WA |
35 ms |
6912 KB |
27.txt |
WA |
68 ms |
6912 KB |
28.txt |
WA |
36 ms |
6784 KB |
29.txt |
WA |
37 ms |
7168 KB |
30.txt |
WA |
69 ms |
7296 KB |
31.txt |
AC |
2 ms |
4352 KB |
32.txt |
AC |
2 ms |
4352 KB |
33.txt |
AC |
2 ms |
4352 KB |
34.txt |
AC |
2 ms |
4352 KB |
s1.txt |
AC |
2 ms |
4352 KB |
s2.txt |
AC |
2 ms |
4352 KB |