QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #888140 | #6240. 游戏 | idusj | 100 ✓ | 172ms | 31176kb | C++14 | 2.1kb | 2025-02-07 22:40:44 | 2025-02-07 22:40:45 |
Judging History
answer
/*
Author: CNYALI_LK
LANG: C++
PROG: game.cpp
Mail: [email protected]
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
int cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
putchar(end);
}
int is[1024242],a[1024242];
int l[1024224],r[1024224],vis[1024242];
void dfs(int x){
if(vis[x])return;
int _l=x,_r=x,ok;
do{
ok=0;
if(_l<=a[_l-1]&&a[_l-1]<=_r){
ok=1;
dfs(_l-1);
_l=l[_l-1];
}
if(_l<=a[_r]&&a[_r]<=_r){
ok=1;
dfs(_r+1);
_r=r[_r+1];
}
}while(ok);
l[x]=_l;
r[x]=_r;
vis[x]=1;
}
int main(){
#ifdef cnyali_lk
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
#endif
int n,m,p,x,y;
n=read();m=read();p=read();
for(int i=1;i<=m;++i){
x=read();y=read();
a[x]=y;
}
is[1]=1;
for(int i=1;i<=n;++i){
is[i+1]=is[i];
if(a[i]){
++is[i+1];
}
}
++m;
for(int i=1;i<=n;++i)if(a[i]){
a[is[i]]=is[a[i]];
}
for(int i=1;i<=m;++i)dfs(i);
while(p){
--p;
x=is[read()];y=is[read()];
if(l[x]<=y&&y<=r[x])printf("YES\n");
else printf("NO\n");
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 11844kb
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: 0ms
memory: 11852kb
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: 14ms
memory: 12932kb
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: 9ms
memory: 17080kb
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: 14ms
memory: 15528kb
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: 12ms
memory: 16264kb
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: 161ms
memory: 30188kb
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: 164ms
memory: 29500kb
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: 172ms
memory: 30692kb
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: 169ms
memory: 31176kb
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