Submission #8395925
Source Code Expand
#include <bits/stdc++.h> #define rg register #define LL long long using namespace std; const int N=200010; const int P=1e9+7; inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; struct node{ int x,y; bool operator < (const node &rhs)const{ return y==rhs.y?x<rhs.x:y<rhs.y; } }b[N],a[N]; int mx[N][21],mn[N][21],sm=1; void ST(){ for(rg int i=1;i<=n;i++) mx[i][0]=mn[i][0]=b[i].x; int t=log2(n)+1; for(rg int j=1;j<t;j++) for(rg int i=1;i+(1<<j)-1<=n;i++){ mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); } } int getmax(int l,int r){ int t=log2(r-l+1); return max(mx[l][t],mx[r-(1<<t)+1][t]); } int getmin(int l,int r){ int t=log2(r-l+1); return min(mn[l][t],mn[r-(1<<t)+1][t]); } struct Binary_Index_Tree{ int c[N]; int lowbit(int x){ return x&(-x); } void update(int x,int d){ while(x<=n){ c[x]=(c[x]+d+P)%P; x+=lowbit(x); } } int query(int x){ int rtn=x>=0; while(x>0){ rtn=(rtn+c[x]+P)%P; x-=lowbit(x); } return rtn; } }T; int main() { n=read(); for(rg int i=1;i<=n;i++) b[i].x=read(),b[i].y=read(); sort(b+1,b+1+n); ST(); for(rg int i=1;i<=n;i++){ a[i].x=a[i].y=i; int l=1,r=i-1; while(l<=r){ int mid=(l+r)>>1; if(getmax(1,mid)>b[i].x)a[i].x=mid,r=mid-1; else l=mid+1; } l=i+1,r=n; while(l<=r){ int mid=(l+r)>>1; if(getmin(mid,r)<b[i].x)a[i].y=mid,l=mid+1; else r=mid-1; } } sort(a+1,a+1+n); for(rg int i=1;i<=n;i++){ int L=a[i].x,R=a[i].y; int nf=(sm-T.query(L-2)+P)%P; sm=(sm+nf)%P; T.update(R,nf); } printf("%d\n",(sm-T.query(n-1)+P)%P); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Mr.Aoki Incubator |
User | luogu_bot2 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1740 Byte |
Status | WA |
Exec Time | 378 ms |
Memory | 36992 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 | 287 ms | 36224 KB |
02.txt | WA | 284 ms | 36224 KB |
03.txt | WA | 281 ms | 36224 KB |
04.txt | WA | 289 ms | 36224 KB |
05.txt | WA | 280 ms | 36224 KB |
06.txt | WA | 285 ms | 36224 KB |
07.txt | WA | 281 ms | 36224 KB |
08.txt | WA | 283 ms | 36224 KB |
09.txt | AC | 303 ms | 36992 KB |
10.txt | AC | 263 ms | 36224 KB |
11.txt | WA | 294 ms | 36992 KB |
12.txt | WA | 307 ms | 36992 KB |
13.txt | WA | 292 ms | 36992 KB |
14.txt | WA | 291 ms | 36992 KB |
15.txt | WA | 303 ms | 36992 KB |
16.txt | WA | 290 ms | 36992 KB |
17.txt | WA | 296 ms | 36992 KB |
18.txt | WA | 306 ms | 36992 KB |
19.txt | WA | 292 ms | 36992 KB |
20.txt | WA | 290 ms | 36992 KB |
21.txt | WA | 316 ms | 36992 KB |
22.txt | WA | 305 ms | 36992 KB |
23.txt | WA | 305 ms | 36992 KB |
24.txt | WA | 312 ms | 36992 KB |
25.txt | WA | 302 ms | 36352 KB |
26.txt | WA | 292 ms | 36352 KB |
27.txt | WA | 378 ms | 36352 KB |
28.txt | WA | 294 ms | 36352 KB |
29.txt | WA | 298 ms | 36608 KB |
30.txt | WA | 350 ms | 36736 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 |