QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #113208 | #6392. Curtains | LFCode | 0 | 47ms | 53440kb | C++14 | 1.9kb | 2023-06-16 17:47:48 | 2023-06-16 17:47:50 |
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 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(){
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: 0
Wrong Answer
time: 8ms
memory: 48416kb
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 NO NO NO NO NO NO NO 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 YES YES NO NO NO YES NO NO NO NO YES YES YES NO YES YES YES...
result:
wrong answer 19th 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: 0
Wrong Answer
time: 47ms
memory: 53440kb
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:
wrong answer 25004th lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%