QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #345287 | #6392. Curtains | ship2077 | 0 | 48ms | 44164kb | C++14 | 1.4kb | 2024-03-06 19:04:20 | 2024-03-06 19:04:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=5e5+5;
vector<int>upd1[M],upd2[M];
vector<pair<int,int>>qry[M];
int n,m,q,l,r,f[M],g[M],stk[M];
bool ans[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
void solve(int l,int r){
if (l>=r) return ;
int mid=l+r>>1;
for (int i=mid,tp=0;i>=l;i--){
f[i]=0x3f3f3f3f;
for (auto j:upd1[i])
if (j>mid) f[i]=min(f[i],j);
else while (tp&&stk[tp]<=j)
f[i]=min(f[i],f[stk[tp--]]);
stk[++tp]=i;
}
for (int i=mid+1,tp=0;i<=r;i++){
g[i]=0;
for (auto j:upd2[i])
if (j<=mid) g[i]=max(g[i],j);
else while (tp&&stk[tp]>=j)
g[i]=max(g[i],g[stk[tp--]]);
stk[++tp]=i;
}
for (int i=l;i<=mid;i++)
for (auto [j,k]:qry[i])
if (j>mid&&j<=r)
ans[k]=f[i]<=j&&g[j]>=i;
solve(l,mid-1);solve(mid+1,r);
}
int main(){
n=read()+1;m=read();q=read();
for (int i=1;i<=m;i++){
l=read();r=read()+1;
upd1[l].push_back(r);
upd2[r].push_back(l);
}
for (int i=1;i<=q;i++){
l=read();r=read()+1;
qry[l].push_back({r,i});
}
solve(1,n);
for (int i=1;i<=q;i++)
puts(ans[i]?"YES":"NO");
return 0;
}
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: 38828kb
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: 4ms
memory: 38744kb
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: -3
Wrong Answer
time: 0ms
memory: 38896kb
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 NO 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:
wrong answer 54th 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
Wrong Answer
Test #32:
score: 20
Accepted
time: 48ms
memory: 43780kb
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: 46ms
memory: 43672kb
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: 44ms
memory: 44164kb
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: -20
Wrong Answer
time: 41ms
memory: 43708kb
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:
wrong answer 88830th lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%