QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #783534 | #6240. 游戏 | 0x3f | 100 ✓ | 258ms | 97312kb | C++14 | 1.7kb | 2024-11-26 10:26:26 | 2024-11-26 10:26:37 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,m,q,pos[N],id[N],o[N],cnt,idx;
int L[N],R[N],ansL[N],ansR[N],vL[N],vR[N],d[N];
vector<int> g[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m>>q;
for(int i=1;i<=m;i++) {
int x,y;
cin>>x>>y;
pos[x]=y;
}
for(int i=1;i<=n;i++) {
int j=i;
cnt++;
while(j+1<=n&&pos[j]==0) j++;
L[cnt]=i,R[cnt]=j;
for(int k=i;k<=j;k++) id[k]=cnt;
i=j;
}
for(int i=1;i<=n;i++)
if(pos[i]!=0) {
int u=id[i],v=id[i+1];
if(pos[i]<=i) {
g[v].push_back(u);
d[u]++;
} else if(pos[i]>i) {
g[u].push_back(v);
d[v]++;
}
}
queue<int> que;
for(int i=1;i<=cnt;i++)
if(d[i]==0)
que.push(i);
while(!que.empty()) {
int u=que.front();
que.pop();
o[++idx]=u;
for(auto v:g[u]) {
d[v]--;
if(d[v]==0)
que.push(v);
}
}
for(int i=1;i<=cnt;i++) ansL[i]=L[i],ansR[i]=R[i];
for(int nw=1;nw<=cnt;nw++) {
int i=o[nw];
int tl=ansL[i],tr=ansR[i];
int lstR=-1;
if(!(pos[tr]>=tl&&pos[tr]<=tr)) lstR=i;
while((pos[tl-1]>=tl&&pos[tl-1]<=tr)||(tr!=lstR)) {
if(pos[tl-1]>=tl&&pos[tl-1]<=tr) {
ansL[i]=ansL[id[tl-1]];
tl=ansL[i];
}
if(pos[tr]>=tl&&pos[tr]<=tr) {
ansR[i]=ansR[id[tr+1]];
lstR=tr;
tr=ansR[i];
}
if(!(pos[tr]>=tl&&pos[tr]<=tr)) lstR=tr;
}
}
for(int i=1;i<=cnt;i++)
for(int j=L[i];j<=R[i];j++)
vL[j]=ansL[i],vR[j]=ansR[i];
while(q--) {
int x,y;
cin>>x>>y;
if(vL[x]<=y&&vR[x]>=y) cout<<"YES\n";
else cout<<"NO\n";
}
// cerr<<"\n"<<clock()<<"ms\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 3ms
memory: 45348kb
input:
1000 699 1000 2 3 3 4 5 18 7 8 8 9 10 151 12 13 16 28 17 18 18 28 24 27 25 26 26 28 27 29 28 29 30 31 31 33 33 50 34 34 35 34 36 36 38 35 41 41 42 42 43 43 44 44 45 45 47 47 49 46 50 45 52 52 53 43 54 45 55 42 57 57 60 55 63 63 64 64 65 65 66 65 67 65 69 64 71 65 73 72 74 74 75 75 76 74 78 78 81 80 ...
output:
YES NO YES NO NO YES NO NO YES NO NO YES NO NO NO YES NO NO YES YES YES NO NO NO NO NO NO YES YES NO YES NO YES NO NO NO YES NO NO YES YES YES NO YES NO NO NO YES NO YES NO NO YES YES NO NO YES YES NO NO YES NO NO NO NO YES YES NO NO NO YES NO NO YES NO NO YES YES YES YES YES YES YES NO NO YES NO NO...
result:
ok 1000 token(s): yes count is 498, no count is 502
Test #2:
score: 10
Accepted
time: 4ms
memory: 45676kb
input:
1000 699 1000 1 3 3 8 4 7 5 9 7 8 9 11 11 210 13 838 14 15 15 16 17 434 18 194 19 668 20 22 22 182 23 24 24 109 26 461 27 28 28 351 30 32 32 35 33 34 34 35 35 38 37 38 38 173 40 84 41 42 42 56 44 45 45 48 47 48 48 49 49 54 51 52 52 53 53 55 55 56 56 57 57 58 58 61 61 63 62 63 63 88 64 72 66 83 67 88...
output:
NO YES YES YES YES YES YES NO YES YES YES NO YES YES NO NO NO YES YES YES NO YES YES NO YES NO NO NO YES NO YES YES NO NO YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES NO NO YES YES NO YES YES YES YES YES NO NO NO NO NO NO YES YES NO YES YES NO YES NO NO YES YES YES NO ...
result:
ok 1000 token(s): yes count is 504, no count is 496
Test #3:
score: 10
Accepted
time: 26ms
memory: 52656kb
input:
100000 89999 100000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 10 9 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 30 29 31 31 32 32 33 33 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 44 44 45 45 46 46 48 47 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 ...
output:
YES YES YES NO NO YES YES YES YES NO YES NO YES YES YES NO NO YES NO NO NO YES NO YES NO NO NO YES NO NO NO YES YES YES YES YES NO YES NO YES NO YES NO YES NO NO NO YES YES NO YES NO NO NO YES NO NO NO NO YES YES NO YES NO NO YES NO NO YES YES NO NO YES YES YES YES YES NO NO YES NO YES NO NO YES YES...
result:
ok 100000 token(s): yes count is 54336, no count is 45664
Test #4:
score: 10
Accepted
time: 19ms
memory: 51832kb
input:
100000 89999 100000 1 1 2 2 4 4 5 5 6 6 7 7 8 8 9 9 10 10 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 34 34 35 35 37 37 38 38 39 39 41 40 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57...
output:
NO YES YES NO YES NO YES NO YES YES YES YES NO YES NO YES NO YES NO YES YES YES NO YES NO NO YES YES YES NO YES NO YES NO NO NO NO YES NO NO YES YES NO NO YES NO YES YES NO NO NO NO NO NO NO YES YES NO YES NO YES NO YES YES NO NO YES YES YES YES NO NO YES YES YES YES NO NO NO NO NO YES YES NO NO NO ...
result:
ok 100000 token(s): yes count is 55025, no count is 44975
Test #5:
score: 10
Accepted
time: 30ms
memory: 52636kb
input:
100000 94999 100000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 5...
output:
NO NO NO NO NO YES NO YES YES NO YES NO YES YES YES NO YES NO YES YES YES YES NO NO YES YES NO NO NO NO YES NO YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO YES NO NO NO NO YES NO NO YES NO NO YES YES YES YES NO NO YES NO NO NO NO NO NO NO YE...
result:
ok 100000 token(s): yes count is 47899, no count is 52101
Test #6:
score: 10
Accepted
time: 19ms
memory: 54256kb
input:
100000 99998 100000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 5...
output:
NO NO YES NO NO NO NO YES NO NO YES NO NO NO YES YES YES YES NO NO NO NO YES NO NO NO NO YES YES NO NO NO NO NO NO NO NO YES NO YES YES NO NO NO NO NO YES NO NO NO YES NO NO YES NO YES YES YES NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO YES YES YES YES YES NO YES YES YES YES NO NO NO NO YES NO Y...
result:
ok 100000 token(s): yes count is 35864, no count is 64136
Test #7:
score: 10
Accepted
time: 253ms
memory: 93752kb
input:
1000000 899999 1000000 1 1 2 2 3 3 5 5 7 6 8 8 10 9 11 11 12 12 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 27 26 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 40 40 42 41 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56...
output:
YES YES YES NO YES NO YES NO NO NO YES YES YES NO NO YES NO NO YES NO YES YES YES NO YES YES YES NO YES NO NO YES NO YES YES NO NO NO NO NO NO YES NO YES NO YES YES YES YES NO YES YES NO NO NO YES NO NO NO YES NO YES YES YES NO NO YES YES YES NO YES NO YES YES NO YES YES NO NO NO YES NO NO NO YES NO...
result:
ok 1000000 token(s): yes count is 544451, no count is 455549
Test #8:
score: 10
Accepted
time: 238ms
memory: 90360kb
input:
1000000 799999 1000000 1 1 3 2 4 4 5 5 6 6 7 7 9 9 11 10 13 12 15 14 16 16 18 17 20 20 21 21 23 22 24 24 25 25 26 26 27 27 29 29 30 30 31 31 32 32 33 33 34 34 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 49 49 50 50 51 51 52 52 54 53 55 55 56 56 57 57 58 58 59 59 61 61 62 ...
output:
NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES NO YES NO YES NO NO NO NO NO YES YES YES NO YES NO YES YES YES YES YES NO NO YES NO YES YES NO YES NO YES YES YES NO YES YES YES NO NO NO NO YES NO NO YES NO YES YES YES NO NO NO NO YES YES YES YES YES NO YES YES NO YES YES YES ...
result:
ok 1000000 token(s): yes count is 550084, no count is 449916
Test #9:
score: 10
Accepted
time: 258ms
memory: 93800kb
input:
1000000 899999 1000000 1 1 2 2 3 3 6 5 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 20 20 21 21 22 22 23 23 24 24 26 25 27 27 28 28 29 29 32 31 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 50 49 51 51 52 52 54 53 55 55 56 56 57 ...
output:
YES NO NO NO YES YES YES NO NO NO YES YES YES NO YES YES NO NO NO NO NO NO YES YES YES YES NO YES YES YES YES YES NO YES NO YES NO NO YES YES YES NO NO YES YES NO YES YES YES NO YES NO NO YES NO NO YES YES YES YES NO YES YES YES YES YES NO YES YES YES NO YES NO YES NO YES NO NO NO NO YES YES YES YES...
result:
ok 1000000 token(s): yes count is 503879, no count is 496121
Test #10:
score: 10
Accepted
time: 238ms
memory: 97312kb
input:
1000000 999999 1000000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 5...
output:
YES NO NO YES NO NO NO NO YES NO NO YES NO YES YES NO YES YES YES YES YES NO NO NO YES NO NO NO YES NO NO NO NO YES YES YES NO YES YES YES YES NO NO YES YES NO NO NO YES YES NO NO YES NO NO YES YES NO NO NO YES YES YES NO YES NO NO NO NO NO NO YES YES YES YES YES YES NO YES NO YES YES NO NO NO NO NO...
result:
ok 1000000 token(s): yes count is 506286, no count is 493714