QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489454#9155. 集合wrhaco100 ✓129ms20856kbC++142.2kb2024-07-24 20:23:182024-07-24 20:23:20

Judging History

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

  • [2024-07-24 20:23:20]
  • 评测
  • 测评结果:100
  • 用时:129ms
  • 内存:20856kb
  • [2024-07-24 20:23:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return x;
}
int n,m,q,A[200010][3],B[200010][3];
int f[200010][3][3],nxt[2][600010],ans[200010];
int cnt,d[2][3];
bool vis[2][3];
vector<int> t;
void init(){
	cnt=0;
	for(int i=0;i<3;i++){
		vis[0][i]=vis[1][i]=0;
	}
	return;
}
void dfs(int x,int tim,int op,int id){
	if(vis[op][id]) return;
	cnt++,vis[op][id]=1;
	for(int i=0;i<3;i++){
		if(op){
			if(f[x][i][id]>tim) dfs(x,tim,0,i);
		}else{
			if(f[x][id][i]>tim) dfs(x,tim,1,i);
		}
	}
	return;
}
inline bool check(int x,int tim){
	for(int i=0;i<3;i++) d[0][i]=d[1][i]=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(f[x][i][j]>tim){
				d[0][i]++,d[1][j]++;
			}
		}
	}
	for(int i=0;i<3;i++){
		init();
		dfs(x,tim,0,i);
		if((d[0][i]<<1)!=cnt) return false;
		init();
		dfs(x,tim,1,i);
		if((d[1][i]<<1)!=cnt) return false;
	}
	return true;
}
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++){
		A[i][0]=read(),A[i][1]=read(),A[i][2]=read();
	}
	for(int i=1;i<=n;i++){
		B[i][0]=read(),B[i][1]=read(),B[i][2]=read();
	}
	for(int i=1;i<=m;i++) nxt[0][i]=nxt[1][i]=n+1;
	for(int i=n;i>=1;i--){
		t.clear();
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(nxt[0][A[i][j]]==nxt[1][B[i][k]]){
					int pos=nxt[0][A[i][j]];
					if(pos==n+1){
						f[i][j][k]=n+1;
					}else{
						for(int J=0;J<3;J++){
							if(A[pos][J]!=A[i][j]) continue;
							for(int K=0;K<3;K++){
								if(B[pos][K]!=B[i][k]) continue;
								f[i][j][k]=f[pos][J][K];
							}
						}
					}
				}else{
					f[i][j][k]=min(nxt[0][A[i][j]],nxt[1][B[i][k]]);
				}
				t.push_back(f[i][j][k]);
			} 
		}
		for(int j=0;j<3;j++) nxt[0][A[i][j]]=nxt[1][B[i][j]]=i;
		sort(t.begin(),t.end());
		for(unsigned int j=0;j<t.size();j++){
			if(j!=t.size()-1&&t[j]==t[j+1]){
				continue;
			}
			if(!check(i,t[j])){
				ans[t[j]]=max(i+1,ans[t[j]]);
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans[i]=max(ans[i],ans[i-1]);
	}
	while(q--){
		int l=read(),r=read();
		puts((ans[r]<=l)?"Yes":"No");
	}
	return 0;
} 

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 11796kb

Pretest #2:

score: 5
Accepted
time: 2ms
memory: 11804kb

Pretest #3:

score: 5
Accepted
time: 2ms
memory: 11768kb

Pretest #4:

score: 5
Accepted
time: 1ms
memory: 11828kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 13844kb

Pretest #6:

score: 5
Accepted
time: 0ms
memory: 11892kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 11872kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 11888kb

Pretest #9:

score: 5
Accepted
time: 4ms
memory: 11812kb

Pretest #10:

score: 5
Accepted
time: 10ms
memory: 11888kb

Pretest #11:

score: 5
Accepted
time: 54ms
memory: 20816kb

Pretest #12:

score: 5
Accepted
time: 57ms
memory: 19568kb

Pretest #13:

score: 5
Accepted
time: 3ms
memory: 13916kb

Pretest #14:

score: 5
Accepted
time: 3ms
memory: 13936kb

Pretest #15:

score: 5
Accepted
time: 47ms
memory: 11824kb

Pretest #16:

score: 5
Accepted
time: 47ms
memory: 11768kb

Pretest #17:

score: 5
Accepted
time: 4ms
memory: 11888kb

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 14124kb

Pretest #19:

score: 5
Accepted
time: 127ms
memory: 20800kb

Pretest #20:

score: 5
Accepted
time: 124ms
memory: 20752kb

Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 11796kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 11888kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 11816kb

Test #4:

score: 5
Accepted
time: 2ms
memory: 11812kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 11760kb

Test #6:

score: 5
Accepted
time: 2ms
memory: 13844kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 11808kb

Test #8:

score: 5
Accepted
time: 0ms
memory: 13932kb

Test #9:

score: 5
Accepted
time: 10ms
memory: 11764kb

Test #10:

score: 5
Accepted
time: 10ms
memory: 13856kb

Test #11:

score: 5
Accepted
time: 57ms
memory: 20188kb

Test #12:

score: 5
Accepted
time: 68ms
memory: 20816kb

Test #13:

score: 5
Accepted
time: 0ms
memory: 11820kb

Test #14:

score: 5
Accepted
time: 3ms
memory: 13856kb

Test #15:

score: 5
Accepted
time: 42ms
memory: 13852kb

Test #16:

score: 5
Accepted
time: 39ms
memory: 13936kb

Test #17:

score: 5
Accepted
time: 9ms
memory: 11968kb

Test #18:

score: 5
Accepted
time: 3ms
memory: 12068kb

Test #19:

score: 5
Accepted
time: 126ms
memory: 20188kb

Test #20:

score: 5
Accepted
time: 129ms
memory: 20856kb

Extra Test:

score: 0
Extra Test Passed