Submission #1368809
Source Code Expand
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<cstdlib> #include<ctime> #include<queue> #include<set> using namespace std; typedef long long LL; const int N=2e5; int gi() { int w=0;bool q=1;char c=getchar(); while ((c<'0'||c>'9') && c!='-') c=getchar(); if (c=='-') q=0,c=getchar(); while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar(); return q? w:-w; } int a[N],b[N],c[N]; int suf[N],d[N],f[N]; pair<int,int>p[N]; int head[N],nxt[N]; bool side[N]; #define x first #define y second int main() { int n=gi(),m,i,j,s,l,r,all=0,cur=0; priority_queue< pair<int,int> >q; for (i=1;i<=n;i++) a[i]=gi(),b[i]=gi(); for (i=1;i<=n+1;i++) c[i]=gi(); sort(c+1,c+1+n+1); for (i=1;i<=n;i++) { a[i]=lower_bound(c+1,c+1+n+1,a[i])-c; b[i]=lower_bound(c+1,c+1+n+1,b[i])-c; d[a[i]-1]--; if (b[i]<a[i]) nxt[i]=head[a[i]-1],head[a[i]-1]=i; side[i]=true; } for (s=-1,i=n+1;i;i--,s++) {//一开始多了一个,每一轮可以抵消一个 s+=d[i]; for (j=head[i];j;j=nxt[j]) q.push(make_pair(-b[j],j)); while (s<-1) //如果<-1则必须把某一个变小 if (q.empty()||-q.top().x>i) { for (m=gi();m--;) puts("-1"); return 0; } else side[q.top().y]=false,s++,d[i]++,d[-q.top().x-1]--,all++,q.pop(); } m=gi(); for (i=n+1;i>=0;i--) d[i]=0; for (i=1;i<=n;i++) d[side[i]?a[i]:b[i]]++; for (i=2;i<=n+1;i++) d[i]+=d[i-1]; while (!q.empty()) q.pop(); for (i=n+1;i;i--) head[i]=0; for (i=1;i<=n;i++) if (side[i]) nxt[i]=head[b[i]],head[b[i]]=i; for (i=1;i<=n+1;i++) { for (j=head[i];j;j=nxt[j]) q.push(make_pair(a[j]-1,j)); f[i]=f[i-1]; if (d[i]-i==-1&&cur<i) { if (q.empty()||q.top().x<i) f[i]=1<<30; else cur=q.top().x,f[i]++,q.pop(); } } while (m--) { l=lower_bound(c+1,c+1+n+1,gi())-c; r=lower_bound(c+1,c+1+n+1,gi())-c; l=f[l-1]+all; r=f[r-1]+all; l=min(l,r+1); if (l>n+1) puts("-1"); else printf("%d\n",n+1-l); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Cards |
User | laofu |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 2018 Byte |
Status | AC |
Exec Time | 117 ms |
Memory | 7540 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 2 ms | 4352 KB |
sample_02.txt | AC | 2 ms | 4352 KB |
sample_03.txt | AC | 2 ms | 4352 KB |
subtask_1_01.txt | AC | 45 ms | 6012 KB |
subtask_1_02.txt | AC | 56 ms | 6008 KB |
subtask_1_03.txt | AC | 25 ms | 5248 KB |
subtask_1_04.txt | AC | 49 ms | 6132 KB |
subtask_1_05.txt | AC | 37 ms | 5372 KB |
subtask_1_06.txt | AC | 80 ms | 6392 KB |
subtask_1_07.txt | AC | 50 ms | 3968 KB |
subtask_1_08.txt | AC | 73 ms | 6520 KB |
subtask_1_09.txt | AC | 74 ms | 6644 KB |
subtask_1_10.txt | AC | 43 ms | 5880 KB |
subtask_1_11.txt | AC | 26 ms | 3200 KB |
subtask_1_12.txt | AC | 39 ms | 5500 KB |
subtask_1_13.txt | AC | 58 ms | 6008 KB |
subtask_1_14.txt | AC | 32 ms | 5496 KB |
subtask_1_15.txt | AC | 38 ms | 3584 KB |
subtask_1_16.txt | AC | 26 ms | 4992 KB |
subtask_1_17.txt | AC | 109 ms | 7412 KB |
subtask_1_18.txt | AC | 26 ms | 5368 KB |
subtask_1_19.txt | AC | 32 ms | 3584 KB |
subtask_1_20.txt | AC | 83 ms | 6648 KB |
subtask_1_21.txt | AC | 112 ms | 7540 KB |
subtask_1_22.txt | AC | 112 ms | 7540 KB |
subtask_1_23.txt | AC | 111 ms | 7540 KB |
subtask_1_24.txt | AC | 112 ms | 7540 KB |
subtask_1_25.txt | AC | 116 ms | 7540 KB |
subtask_1_26.txt | AC | 112 ms | 7412 KB |
subtask_1_27.txt | AC | 53 ms | 4224 KB |
subtask_1_28.txt | AC | 112 ms | 7160 KB |
subtask_1_29.txt | AC | 117 ms | 7540 KB |
subtask_1_30.txt | AC | 111 ms | 7412 KB |
subtask_1_31.txt | AC | 53 ms | 4224 KB |
subtask_1_32.txt | AC | 112 ms | 7160 KB |
subtask_1_33.txt | AC | 116 ms | 7540 KB |
subtask_1_34.txt | AC | 112 ms | 7284 KB |
subtask_1_35.txt | AC | 53 ms | 4224 KB |
subtask_1_36.txt | AC | 112 ms | 7160 KB |
subtask_1_37.txt | AC | 117 ms | 7540 KB |
subtask_1_38.txt | AC | 111 ms | 7284 KB |
subtask_1_39.txt | AC | 53 ms | 4224 KB |
subtask_1_40.txt | AC | 113 ms | 7160 KB |
subtask_1_41.txt | AC | 92 ms | 7540 KB |
subtask_1_42.txt | AC | 86 ms | 7412 KB |
subtask_1_43.txt | AC | 101 ms | 7540 KB |
subtask_1_44.txt | AC | 84 ms | 7160 KB |
subtask_1_45.txt | AC | 42 ms | 4224 KB |
subtask_1_46.txt | AC | 85 ms | 7540 KB |
subtask_1_47.txt | AC | 75 ms | 7540 KB |
subtask_1_48.txt | AC | 91 ms | 7540 KB |
subtask_1_49.txt | AC | 77 ms | 7412 KB |
subtask_1_50.txt | AC | 37 ms | 4224 KB |
subtask_1_51.txt | AC | 2 ms | 4352 KB |
subtask_1_52.txt | AC | 2 ms | 4352 KB |
subtask_1_53.txt | AC | 2 ms | 4352 KB |
subtask_1_54.txt | AC | 2 ms | 4352 KB |
subtask_1_55.txt | AC | 2 ms | 4352 KB |