QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112980 | #6392. Curtains | LFCode | 0 | 1012ms | 286512kb | C++14 | 3.6kb | 2023-06-15 17:19:46 | 2023-06-16 14:56:17 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using std::vector;
using std::set;
const int N=500086,INF=1e9+7;
int n,m,q,il[N],ir[N],pre[N],suf[N],ml[N],mr[N],ql[N],qr[N],mnl[N<<2],mxr[N<<2];
bool ans[N];
vector<int>vec[N<<2],iv[N<<2];
set<int>s[N<<2];
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){//询问插入至分治lca
int mid=(l+r)>>1;if(ql[x]<=mid&&qr[x]>mid||l==r){vec[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 pushiv(int k,int l,int r,int x){//区间插入至分治lca
int mid=(l+r)>>1;if(il[x]<=mid&&ir[x]>mid||l==r){iv[k].push_back(x);return true;}
return ir[x]<=mid?pushiv(k<<1,l,mid,x):pushiv(k<<1|1,mid+1,r,x);
}
bool pushp(int k,int l,int r,int x,int y){//二维数点预备
s[k].insert(y);if(l==r)return true;int mid=(l+r)>>1;
return x<=mid?pushp(k<<1,l,mid,x,y):pushp(k<<1|1,mid+1,r,x,y);
}
bool ask(int k,int l,int r,int x,int y,int a,int b){//二维数点
if(l>=x&&r<=y){
set<int>::iterator it=s[k].lower_bound(a);
if(it!=s[k].end())return (*it)<=b;return false;
}
int mid=(l+r)>>1;bool ret=false;
if(x<=mid)ret|=ask(k<<1,l,mid,x,y,a,b);
if(mid<y)ret|=ask(k<<1|1,mid+1,r,x,y,a,b);
return ret;
}
bool build(int k,int l,int r){
mnl[k]=INF;if(l==r)return true;int mid=(l+r)>>1;
return build(k<<1,l,mid)&build(k<<1|1,mid+1,r);
}
bool pushl(int k,int l,int r,int x,int y){
mxr[k]=Max(mxr[k],y);if(l==r)return true;int mid=(l+r)>>1;
return x<=mid?pushl(k<<1,l,mid,x,y):pushl(k<<1|1,mid+1,r,x,y);
}
bool pushr(int k,int l,int r,int x,int y){
mnl[k]=Min(mnl[k],x);if(l==r)return true;int mid=(l+r)>>1;
return y<=mid?pushr(k<<1,l,mid,x,y):pushr(k<<1|1,mid+1,r,x,y);
}
int gml(int k,int l,int r,int x,int y){
if(x>y)x=y;if(l>=x&&r<=y)return mnl[k];int mid=(l+r)>>1,ret=INF;
if(x<=mid)ret=Min(ret,gml(k<<1,l,mid,x,y));
if(mid<y)ret=Min(ret,gml(k<<1|1,mid+1,r,x,y));
return ret;
}
int gmr(int k,int l,int r,int x,int y){
if(x>y)y=x;if(l>=x&&r<=y)return mxr[k];int mid=(l+r)>>1,ret=0;
if(x<=mid)ret=Max(ret,gmr(k<<1,l,mid,x,y));
if(mid<y)ret=Max(ret,gmr(k<<1|1,mid+1,r,x,y));
return ret;
}
bool Div(int k,int l,int r){//分治
if(l==r){
if(!iv[k].empty())ml[l]=mr[l]=l;pushl(1,1,n,l,r);pushr(1,1,n,l,r);
for(vector<int>::iterator it=vec[k].begin();it!=vec[k].end();it++)
ans[*it]=ask(k,l,r,l,r,l,r);
return true;
}
int mid=(l+r)>>1;Div(k<<1,l,mid);Div(k<<1|1,mid+1,r);
for(vector<int>::iterator it=vec[k].begin();it!=vec[k].end();it++)
ans[*it]=ask(k,l,r,ql[*it],mr[ql[*it]]+1,ml[qr[*it]]-1,qr[*it]);
for(vector<int>::iterator it=iv[k].begin();it!=iv[k].end();it++){
pushl(1,1,n,il[*it],ir[*it]);
pushr(1,1,n,il[*it],ir[*it]);
}
suf[mid]=ml[mid];pre[mid]=0;
for(int i=mid-1;i>=l;i--)suf[i]=Min(suf[i+1],ml[i]);//后缀ml最小值
for(int i=mid+1;i<=r;i++)pre[i]=Max(pre[i-1],mr[i]);//前缀mr最大值
for(int i=mid;i>=l;i--){int rp=gmr(k,l,r,i,mr[i]);if(rp>mid)mr[i]=Max(rp,pre[rp]);}
for(int i=mid+1;i<=r;i++){int lp=gml(k,l,r,ml[i],i);if(lp<=mid)ml[i]=Min(lp,suf[lp]);}
return true;
}
int main(){
n=read();m=read();q=read();build(1,1,n);
for(int i=1;i<=m;i++){il[i]=read();ir[i]=read();pushp(1,1,n,il[i],ir[i]);pushiv(1,1,n,i);}
for(int i=1;i<=q;i++){ql[i]=read();qr[i]=read();pushq(1,1,n,i);}
for(int i=1;i<=n;i++){ml[i]=i+1;mr[i]=i-1;}
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: 28ms
memory: 208568kb
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 NO NO NO NO NO NO 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 NO 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 YES N...
result:
wrong answer 14th 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: 1012ms
memory: 286512kb
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 NO 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 YES...
result:
wrong answer 33rd lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%