QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112982#6392. CurtainsLFCode0 1003ms290408kbC++143.6kb2023-06-15 17:24:102023-06-16 14:56:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 14:56:20]
  • 评测
  • 测评结果:0
  • 用时:1003ms
  • 内存:290408kb
  • [2023-06-15 17:24:10]
  • 提交

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(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(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]);suf[l-1]=suf[l];//后缀ml最小值
	for(int i=mid+1;i<=r;i++)pre[i]=Max(pre[i-1],mr[i]);pre[r+1]=pre[r];//前缀mr最大值
	for(int i=mid;i>=l;i--){int rp=gmr(k,l,r,i,mr[i]+1);if(rp>mid)mr[i]=Max(rp,pre[rp+1]);}
	for(int i=mid+1;i<=r;i++){int lp=gml(k,l,r,ml[i]-1,i);if(lp<=mid)ml[i]=Min(lp,suf[lp-1]);}
	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: 25ms
memory: 209892kb

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: 1003ms
memory: 290408kb

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%