QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506286#9155. 集合Sheez_Official100 ✓235ms19320kbC++141.1kb2024-08-05 16:27:052024-08-05 16:27:05

Judging History

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

  • [2024-08-05 16:27:05]
  • 评测
  • 测评结果:100
  • 用时:235ms
  • 内存:19320kb
  • [2024-08-05 16:27:05]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=6e5+10;
int n,m,q,a[N][3],b[N][3],ha[N],hb[N],w[N],ans[N],mod=998244353,now;

void plua(int i,int k){
	for(int j=0;j<3;j++){
		now=(now-1ll*ha[a[i][j]]*ha[a[i][j]]%mod*ha[a[i][j]]%mod+mod)%mod;
		ha[a[i][j]]=((ha[a[i][j]]+k*w[i])%mod+mod)%mod;
		now=(now+1ll*ha[a[i][j]]*ha[a[i][j]]%mod*ha[a[i][j]]%mod)%mod;
	}
}
void plub(int i,int k){
	for(int j=0;j<3;j++){
		now=(now+1ll*hb[b[i][j]]*hb[b[i][j]]%mod*hb[b[i][j]]%mod)%mod;
		hb[b[i][j]]=((hb[b[i][j]]+k*w[i])%mod+mod)%mod;
		now=(now-1ll*hb[b[i][j]]*hb[b[i][j]]%mod*hb[b[i][j]]%mod+mod)%mod;
	}
}
void add(int i,int k){
	plua(i,k),plub(i,k);
}

signed main(){
	scanf("%d%d%d",&n,&m,&q);
	mt19937 rnd(random_device{}());
	for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
	for(int i=1;i<=n;i++)w[i]=(1ll*rnd()*rnd()%mod+rnd())%mod;
	for(int l=1,r=0;l<=n;l++){
		while(r<=n&&!now)add(++r,1);
		ans[l]=r-1;
		add(l,-1);
	}
	while(q--){int l,r;scanf("%d%d",&l,&r);puts(ans[l]>=r?"Yes":"No");}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 21ms
memory: 9820kb

Pretest #10:

score: 5
Accepted
time: 21ms
memory: 9828kb

Pretest #11:

score: 5
Accepted
time: 103ms
memory: 16344kb

Pretest #12:

score: 5
Accepted
time: 119ms
memory: 14740kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 105ms
memory: 9760kb

Pretest #16:

score: 5
Accepted
time: 105ms
memory: 9840kb

Pretest #17:

score: 5
Accepted
time: 12ms
memory: 11884kb

Pretest #18:

score: 5
Accepted
time: 8ms
memory: 10420kb

Pretest #19:

score: 5
Accepted
time: 221ms
memory: 16756kb

Pretest #20:

score: 5
Accepted
time: 235ms
memory: 18260kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 21ms
memory: 9824kb

Test #10:

score: 5
Accepted
time: 18ms
memory: 9824kb

Test #11:

score: 5
Accepted
time: 111ms
memory: 16908kb

Test #12:

score: 5
Accepted
time: 115ms
memory: 16756kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 104ms
memory: 9812kb

Test #16:

score: 5
Accepted
time: 100ms
memory: 9920kb

Test #17:

score: 5
Accepted
time: 11ms
memory: 9888kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 210ms
memory: 14760kb

Test #20:

score: 5
Accepted
time: 233ms
memory: 19320kb

Extra Test:

score: 0
Extra Test Passed