QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112986 | #6392. Curtains | LFCode | 3 | 1074ms | 290184kb | C++14 | 3.8kb | 2023-06-15 17:47:25 | 2023-06-16 14:56:24 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using std::vector;
using std::set;
const int N=500086,INF=1e9+7;
int n,m,q,il[N],ir[N],pre[N],suf[N],ml[N],mr[N],ql[N],qr[N],mnl[N<<2],mxr[N<<2];
bool ans[N];
vector<int>vec[N<<2],iv[N<<2];
set<int>s[N<<2];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
bool pushq(int k,int l,int r,int x){//询问插入至分治lca
int mid=(l+r)>>1;if(ql[x]<=mid&&qr[x]>mid||l==r){vec[k].push_back(x);return true;}
return qr[x]<=mid?pushq(k<<1,l,mid,x):pushq(k<<1|1,mid+1,r,x);
}
bool pushiv(int k,int l,int r,int x){//区间插入至分治lca
int mid=(l+r)>>1;if(il[x]<=mid&&ir[x]>mid||l==r){iv[k].push_back(x);return true;}
return ir[x]<=mid?pushiv(k<<1,l,mid,x):pushiv(k<<1|1,mid+1,r,x);
}
bool pushp(int k,int l,int r,int x,int y){//二维数点预备
s[k].insert(y);if(l==r)return true;int mid=(l+r)>>1;
return x<=mid?pushp(k<<1,l,mid,x,y):pushp(k<<1|1,mid+1,r,x,y);
}
bool ask(int k,int l,int r,int x,int y,int a,int b){//二维数点
if(l>=x&&r<=y){
set<int>::iterator it=s[k].lower_bound(a);
if(it!=s[k].end())return (*it)<=b;return false;
}
int mid=(l+r)>>1;bool ret=false;
if(x<=mid)ret|=ask(k<<1,l,mid,x,y,a,b);
if(mid<y)ret|=ask(k<<1|1,mid+1,r,x,y,a,b);
return ret;
}
bool build(int k,int l,int r){
mnl[k]=INF;if(l==r)return true;int mid=(l+r)>>1;
return build(k<<1,l,mid)&build(k<<1|1,mid+1,r);
}
bool pushl(int k,int l,int r,int x,int y){
mxr[k]=Max(mxr[k],y);if(l==r)return true;int mid=(l+r)>>1;
return x<=mid?pushl(k<<1,l,mid,x,y):pushl(k<<1|1,mid+1,r,x,y);
}
bool pushr(int k,int l,int r,int x,int y){
mnl[k]=Min(mnl[k],x);if(l==r)return true;int mid=(l+r)>>1;
return y<=mid?pushr(k<<1,l,mid,x,y):pushr(k<<1|1,mid+1,r,x,y);
}
int gml(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return mnl[k];int mid=(l+r)>>1,ret=INF;
if(x<=mid)ret=Min(ret,gml(k<<1,l,mid,x,y));
if(mid<y)ret=Min(ret,gml(k<<1|1,mid+1,r,x,y));
return ret;
}
int gmr(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return mxr[k];int mid=(l+r)>>1,ret=0;
if(x<=mid)ret=Max(ret,gmr(k<<1,l,mid,x,y));
if(mid<y)ret=Max(ret,gmr(k<<1|1,mid+1,r,x,y));
return ret;
}
bool Div(int k,int l,int r){//分治
if(l==r){
if(!iv[k].empty()){ml[l]=mr[l]=l;pushl(1,1,n,l,r);pushr(1,1,n,l,r);}
for(vector<int>::iterator it=vec[k].begin();it!=vec[k].end();it++)
ans[*it]=ask(k,l,r,l,r,l,r);
return true;
}
int mid=(l+r)>>1;Div(k<<1,l,mid);Div(k<<1|1,mid+1,r);
for(vector<int>::iterator it=vec[k].begin();it!=vec[k].end();it++){
int nl=ql[*it],nr=qr[*it];
ans[*it]=ask(k,l,r,nl,mr[nl]+1,ml[nr]-1,nr);if(ans[*it])continue;
if(ask(k,l,r,nl,mr[nl]+1,mid+1,nr)&&ask(k,l,r,nl,mid,ml[nr]-1,nr))ans[*it]=true;
}
for(vector<int>::iterator it=iv[k].begin();it!=iv[k].end();it++){
pushl(1,1,n,il[*it],ir[*it]);
pushr(1,1,n,il[*it],ir[*it]);
}
suf[mid]=ml[mid];pre[mid]=0;
for(int i=mid-1;i>=l;i--)suf[i]=Min(suf[i+1],ml[i]);suf[l-1]=suf[l];//后缀ml最小值
for(int i=mid+1;i<=r;i++)pre[i]=Max(pre[i-1],mr[i]);pre[r+1]=pre[r];//前缀mr最大值
for(int i=mid;i>=l;i--){int rp=gmr(k,l,r,i,mr[i]+1);if(rp>mid)mr[i]=Max(rp,pre[rp+1]);}
for(int i=mid+1;i<=r;i++){int lp=gml(k,l,r,ml[i]-1,i);if(lp<=mid)ml[i]=Min(lp,suf[lp-1]);}
return true;
}
int main(){
n=read();m=read();q=read();build(1,1,n);
for(int i=1;i<=m;i++){il[i]=read();ir[i]=read();pushp(1,1,n,il[i],ir[i]);pushiv(1,1,n,i);}
for(int i=1;i<=q;i++){ql[i]=read();qr[i]=read();pushq(1,1,n,i);}
for(int i=1;i<=n;i++){ml[i]=i+1;mr[i]=i-1;}
Div(1,1,n);for(int i=1;i<=q;i++)if(ans[i])puts("YES");else puts("NO");
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 25ms
memory: 208504kb
input:
200 200 200 113 134 77 77 110 143 126 157 122 131 161 172 59 134 19 68 117 142 15 103 61 182 12 67 73 97 72 128 68 110 19 137 14 118 60 150 42 64 25 30 118 158 149 164 79 149 21 94 33 82 3 130 36 142 57 170 64 140 40 98 115 132 2 45 27 85 43 181 120 125 82 160 121 176 16 154 59 74 34 52 71 74 57 185...
output:
NO YES NO NO YES NO NO NO YES NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO YES YES NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO NO YES YES YES NO YES YES YE...
result:
ok 200 lines
Test #2:
score: 0
Accepted
time: 16ms
memory: 208600kb
input:
200 200 200 177 200 1 17 123 127 19 53 172 177 4 16 44 132 97 124 94 143 15 71 96 140 61 181 109 162 28 95 108 162 24 146 84 107 20 154 92 118 133 141 55 58 73 154 35 86 83 124 9 90 92 114 46 81 35 62 45 83 11 52 11 178 35 188 128 156 20 87 102 150 22 157 21 34 7 174 27 48 2 75 159 191 30 95 140 153...
output:
YES NO NO NO NO NO NO NO YES NO YES YES YES NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO YES NO YES NO YES NO NO NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO YES NO YES NO NO NO NO YES NO YES NO NO NO NO NO NO YES NO YES NO NO YES Y...
result:
ok 200 lines
Test #3:
score: 0
Accepted
time: 18ms
memory: 209840kb
input:
200 200 200 74 143 108 109 6 95 85 155 130 172 73 186 14 51 73 147 61 108 7 158 28 28 66 149 84 192 79 196 94 126 7 86 102 199 27 49 32 163 90 198 137 179 57 123 41 75 33 190 20 175 84 154 163 184 70 83 76 154 77 105 49 164 67 191 22 157 38 83 60 99 50 129 10 32 25 154 10 122 155 174 111 124 63 135 ...
output:
YES NO YES NO NO NO NO NO NO NO YES NO YES NO NO YES YES NO NO YES NO NO YES NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO YES YES YES NO NO NO YES YES NO NO NO YES NO YES NO NO YES NO NO YES NO YES NO YES NO NO NO NO YES NO YES NO...
result:
ok 200 lines
Test #4:
score: 0
Accepted
time: 24ms
memory: 209116kb
input:
200 200 200 177 181 118 129 13 72 3 80 18 82 6 7 89 182 97 184 132 150 4 54 129 132 83 136 14 119 15 19 67 123 176 198 41 51 81 129 155 170 20 187 85 111 96 163 195 200 34 179 39 186 35 87 90 93 3 191 21 187 1 100 193 195 57 61 52 159 40 188 117 182 106 112 92 111 105 136 106 170 86 113 39 42 107 11...
output:
YES NO NO YES NO YES NO YES NO YES YES NO NO YES YES NO YES NO NO NO YES NO YES NO NO NO NO NO NO YES NO YES NO NO YES NO YES YES YES NO YES NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES NO NO NO NO NO YES YES YES NO YES NO NO NO NO NO NO NO YES NO NO YES YES NO Y...
result:
ok 200 lines
Test #5:
score: 0
Accepted
time: 20ms
memory: 208232kb
input:
200 200 200 116 119 160 161 27 79 20 194 98 100 9 127 106 139 32 33 14 162 3 71 82 133 88 137 129 163 174 175 3 20 100 111 11 191 24 28 135 136 117 143 31 147 44 47 111 116 100 175 40 165 129 197 87 89 61 175 91 93 14 105 193 195 48 92 71 72 67 82 101 153 67 160 64 66 136 137 128 197 35 153 195 199 ...
output:
YES NO YES NO NO NO YES YES YES NO YES YES NO NO YES NO NO NO NO YES YES YES NO YES NO YES NO NO NO NO YES YES NO NO YES NO YES NO YES NO NO NO YES YES YES NO NO NO YES YES YES YES YES NO YES NO NO NO YES NO NO YES YES YES NO NO NO NO NO YES NO NO YES NO YES NO YES YES NO YES NO YES YES YES NO NO NO...
result:
ok 200 lines
Test #6:
score: 0
Accepted
time: 16ms
memory: 208172kb
input:
200 200 200 18 98 42 142 96 162 170 184 6 35 113 155 16 136 22 177 36 95 50 114 44 76 17 44 87 173 124 189 20 48 47 101 66 188 68 138 100 171 23 49 67 184 119 189 47 81 24 27 58 122 38 95 12 96 90 131 16 165 46 86 33 59 25 122 126 145 132 190 32 114 45 183 22 36 27 199 190 193 22 126 60 80 58 179 22...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200 lines
Test #7:
score: 0
Accepted
time: 20ms
memory: 209664kb
input:
200 200 200 102 106 7 10 88 91 135 136 129 136 90 99 6 6 135 145 80 85 2 5 53 53 146 146 23 27 178 186 19 22 139 148 34 37 59 66 170 178 135 136 131 138 180 182 90 98 171 177 28 28 179 181 177 182 171 181 107 117 3 3 59 63 100 104 124 129 195 200 150 156 162 165 140 145 71 74 94 100 52 60 24 34 69 7...
output:
YES NO NO NO YES NO NO YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES NO NO YES YES NO YES NO YES NO YES NO YES YES NO NO YES YES NO NO YES YES YES YES YES NO NO YES NO NO NO NO NO YES YES NO NO NO NO YES NO YES NO NO NO YES NO YES YES YES...
result:
ok 200 lines
Test #8:
score: 0
Accepted
time: 16ms
memory: 208228kb
input:
200 200 200 123 125 128 131 157 165 37 47 31 34 200 200 13 14 184 194 145 153 39 41 8 18 117 122 26 33 173 179 150 152 31 37 52 53 169 175 45 51 198 199 53 60 98 104 74 74 4 5 184 188 105 110 14 21 116 119 142 150 168 172 121 130 56 65 145 152 89 90 126 129 130 130 50 53 154 163 21 22 170 172 71 79 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200 lines
Test #9:
score: 0
Accepted
time: 20ms
memory: 209636kb
input:
200 200 200 150 150 127 127 102 102 62 62 47 47 192 192 63 63 50 50 37 37 173 173 169 169 66 66 183 183 171 171 104 104 75 75 184 184 128 128 57 57 197 197 163 163 193 193 199 199 153 153 25 25 175 175 98 98 80 80 120 120 106 106 181 181 113 113 143 143 130 130 121 121 185 185 172 172 78 78 125 125 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 200 lines
Test #10:
score: 0
Accepted
time: 21ms
memory: 209652kb
input:
200 100 200 150 159 165 174 79 88 29 38 64 73 157 166 59 68 102 111 159 168 60 69 116 125 134 143 190 199 65 74 114 123 176 185 2 11 97 106 166 175 31 40 152 161 47 56 68 77 126 135 10 19 81 90 178 187 70 79 101 110 75 84 169 178 90 99 73 82 103 112 172 181 16 25 141 150 143 152 167 176 23 32 37 46 ...
output:
YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO YES NO YES YES YES YES NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO ...
result:
ok 200 lines
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #11:
score: 0
Wrong Answer
time: 31ms
memory: 209172kb
input:
2000 2000 2000 135 211 509 982 410 1776 192 1071 20 1129 821 872 407 1514 1321 1333 1425 1437 28 1936 655 1360 1353 1426 327 550 1036 1431 806 1791 1242 1247 371 651 622 1589 1491 1538 820 1828 431 1346 660 1372 712 1768 1414 1847 1329 1672 570 592 76 1838 427 1549 955 1598 790 1165 828 1784 1818 19...
output:
NO NO NO NO NO NO NO YES YES NO NO NO YES NO NO NO NO NO YES YES NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO YES NO NO NO NO YES NO NO NO NO...
result:
wrong answer 150th lines differ - expected: 'YES', found: 'NO'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #32:
score: 20
Accepted
time: 1063ms
memory: 290184kb
input:
100000 100000 100000 44237 85021 45776 80409 39632 94735 28119 63770 47399 73347 28902 87358 27924 65499 23898 54817 50114 96633 11325 37690 46642 94643 9271 47594 47324 47948 27957 58134 20443 88720 20834 89483 77577 94705 7835 30030 37387 59648 8364 76478 66145 76025 12683 79475 1745 33181 43966 5...
output:
YES NO YES NO YES YES YES YES YES YES NO NO YES YES YES YES NO NO YES NO NO YES NO YES NO YES YES YES NO NO YES NO YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO YES NO YES YES YES YES YES YES NO YES NO NO NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO NO NO NO YES NO YES NO YE...
result:
ok 100000 lines
Test #33:
score: 0
Accepted
time: 1074ms
memory: 289184kb
input:
100000 100000 100000 35741 60377 60963 75253 19797 42601 35753 79403 7502 18877 47102 89341 28014 35036 2734 26925 1088 30541 8270 68412 10391 85525 50950 55103 57533 94509 52355 77010 77860 88590 8709 31105 4292 21010 438 9944 34758 94378 31011 98475 37243 73734 21568 46633 59934 94265 3839 68210 2...
output:
YES NO YES NO YES NO YES YES NO NO NO NO NO YES NO NO NO NO YES NO NO YES YES NO NO NO NO YES NO NO YES YES YES NO NO NO NO NO NO NO YES NO NO NO YES NO YES YES YES YES YES NO NO YES NO NO NO NO YES NO NO NO NO NO NO YES YES YES NO YES YES NO YES NO YES NO NO NO NO NO NO YES NO YES NO NO YES NO NO N...
result:
ok 100000 lines
Test #34:
score: 0
Accepted
time: 713ms
memory: 270308kb
input:
100000 100000 100000 18975 18982 81626 81634 78338 78345 51904 51907 21622 21626 9459 9461 83080 83081 60411 60421 34363 34365 33780 33783 93124 93133 65357 65367 37292 37297 55530 55536 5618 5622 24035 24043 11654 11659 17731 17738 23791 23801 16233 16236 7398 7400 57194 57202 537 541 70637 70638 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 100000 lines
Test #35:
score: 0
Accepted
time: 609ms
memory: 261356kb
input:
100000 100000 100000 56780 56781 78108 78113 38474 38474 71772 71772 46509 46509 31045 31052 39368 39377 8043 8043 34076 34081 29173 29175 74381 74381 97949 97952 76876 76880 47094 47103 89482 89482 21332 21335 51072 51072 21495 21498 44772 44774 29483 29492 15061 15071 98370 98375 7980 7989 44782 4...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 100000 lines
Test #36:
score: 0
Accepted
time: 703ms
memory: 269760kb
input:
100000 100000 100000 13478 13486 66101 66103 29480 29483 67830 67834 44111 44115 74416 74422 18008 18011 23931 23932 34645 34649 69377 69379 18187 18197 7908 7913 27349 27359 75638 75645 47967 47969 10462 10467 7179 7183 90906 90912 17936 17943 29688 29692 91894 91897 38747 38748 85436 85443 52049 5...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 100000 lines
Test #37:
score: 0
Accepted
time: 595ms
memory: 261736kb
input:
100000 100000 100000 35164 35164 35404 35408 44222 44227 73177 73185 64265 64271 80552 80553 23132 23140 29501 29509 36283 36290 54724 54729 39668 39678 95694 95703 35921 35921 94533 94541 26515 26516 49429 49431 79417 79422 37677 37681 8230 8238 56125 56128 87102 87109 66148 66155 16156 16160 59157...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 100000 lines
Test #38:
score: -20
Time Limit Exceeded
input:
500000 500000 500000 88682 403281 274991 471113 5603 53417 99204 205233 29613 32231 400245 490999 100888 117309 52 4642 11996 165917 214488 475381 264403 381213 65798 375601 5707 203306 31302 110300 347251 490260 338382 376148 191679 232337 111617 135636 140646 479165 86807 475274 244419 453460 1871...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%