QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #113392 | #6392. Curtains | LFCode | 0 | 321ms | 69688kb | C++14 | 1.9kb | 2023-06-17 13:57:16 | 2023-06-17 13:57:18 |
Judging History
answer
#include<cstdio>
#include<vector>
using std::vector;
const int N=500086;
int n,m,q,st[N],ql[N],qr[N],mxl[N],mnr[N],ans[N];
bool p[N];
vector<int>vl[N],vr[N],vq[N];
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){
int mid=(l+r)>>1;if(l==r||(ql[x]<=mid&&qr[x]>=mid)){vq[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 Div(int k,int l,int r){
if(l==r){
if(p[l])
for(vector<int>::iterator it=vq[k].begin();it!=vq[k].end();it++)
ans[*it]=true;
return true;
}
int mid=(l+r)>>1;Div(k<<1,l,mid);Div(k<<1|1,mid+1,r);
for(int i=mid,tp=0;i>=l;i--){
mnr[i]=r+1;int mr=0;
for(vector<int>::iterator it=vl[i].begin();it!=vl[i].end();it++){
if(*it>r)continue;
if(*it<mid)mr=Max(mr,*it);else mnr[i]=Min(mnr[i],*it);
}
while(tp&&(st[tp]<=mr+1||mnr[st[tp]]>=mnr[i]))mnr[i]=Min(mnr[i],mnr[st[tp--]]);
st[++tp]=i;
}
for(int i=mid+1,tp=0;i<=r;i++){
mxl[i]=0;int ml=r+1;
for(vector<int>::iterator it=vr[i].begin();it!=vr[i].end();it++){
if(*it<l)continue;
if(*it>mid+1)ml=Min(ml,*it);else mxl[i]=Max(mxl[i],*it);
}
while(tp&&(st[tp]>=ml-1||mxl[st[tp]]<=mxl[i]))mxl[i]=Max(mxl[i],mxl[st[tp--]]);
st[++tp]=i;
}
for(vector<int>::iterator it=vq[k].begin();it!=vq[k].end();it++)
ans[*it]=mnr[ql[*it]]<=qr[*it]&&mxl[qr[*it]]>=ql[*it];
return true;
}
int main(){
// freopen("data.in","r",stdin);
n=read();m=read();q=read();
for(int i=1;i<=m;i++){
int l=read();int r=read();if(l==r)p[l]=true;
vl[l].push_back(r);vr[r].push_back(l);
}
for(int i=1;i<=q;i++){ql[i]=read();qr[i]=read();pushq(1,1,n,i);}
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: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 0ms
memory: 49048kb
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: 7ms
memory: 49484kb
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: 4ms
memory: 48708kb
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: -3
Wrong Answer
time: 3ms
memory: 48356kb
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 NO 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 NO YES NO NO NO NO NO YES YES YES NO YES NO NO NO NO NO NO NO YES NO NO YES YES NO YES...
result:
wrong answer 4th lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #32:
score: 20
Accepted
time: 50ms
memory: 53996kb
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: 45ms
memory: 52424kb
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: 45ms
memory: 53428kb
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: 44ms
memory: 52268kb
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: 42ms
memory: 53468kb
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: 38ms
memory: 53320kb
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: 0
Accepted
time: 316ms
memory: 69688kb
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:
NO YES NO NO NO NO YES NO NO YES YES NO YES NO YES NO NO YES NO NO NO NO NO YES NO NO YES NO YES NO YES YES NO NO YES YES YES NO NO NO NO NO NO YES NO YES NO YES NO NO YES NO NO YES YES YES NO YES NO YES NO YES NO NO YES YES NO NO NO YES NO NO NO NO YES NO NO NO YES NO YES NO NO NO YES NO NO YES NO ...
result:
ok 500000 lines
Test #39:
score: 0
Accepted
time: 321ms
memory: 68196kb
input:
500000 500000 500000 204810 419422 251667 437173 32193 354856 9920 283192 333795 466386 235797 284143 176786 219551 166453 447969 259718 413475 112506 272325 187989 444962 206011 249984 82571 348619 180355 204521 114417 480380 162226 357608 74629 135111 161937 449322 338017 346599 62512 376917 13834...
output:
NO YES YES YES YES YES YES NO NO NO NO NO YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES NO YES NO YES YES YES YES NO NO YES NO NO YES NO NO YES YES NO YES YES YES NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO YES NO YES NO NO NO YES YES NO YES YES NO NO NO YES NO NO YES NO NO YES YES...
result:
ok 500000 lines
Test #40:
score: -20
Runtime Error
input:
500000 500000 500000 390239 390243 392690 392699 75406 75411 37104 37108 159174 159179 202000 202004 37441 37443 67196 67196 142641 142643 362951 362960 113852 113858 425802 425808 356011 356018 238911 238919 10572 10573 326437 326447 446222 446227 76031 76039 228180 228189 393618 393628 476528 4765...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%