QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526902#9155. 集合ChiFAN100 ✓491ms87528kbC++142.9kb2024-08-22 00:55:042024-08-22 00:55:04

Judging History

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

  • [2024-08-22 00:55:04]
  • 评测
  • 测评结果:100
  • 用时:491ms
  • 内存:87528kb
  • [2024-08-22 00:55:04]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
int mod = 998244353;
int Mod = 1e18+7;
int C1,C2,C3;
//#define lowbit(x) (x&(-x))
using namespace std;
int Hash(int x){
	return (((x+C1)%mod)*((x+C2)%mod)%Mod+((x>>1+x/2+x/5)%mod)*((x^C3)%mod)%Mod)%Mod;
}
const int maxn = 2e5+114;
const int maxm = 6e5+114;
const int maxq = 1e6+114;
int a[maxn][3],b[maxn][3];
int value[maxn],n,m,q;
mt19937 rd(time(0));
int val[maxm][2];
int R[maxn],l,r;
string answer[maxq];
int valuea,valueb;
vector< pair<int,int> > ask[maxn];//(r,id)
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	C1=rd(),C2=rd(),C3=rd();
	for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2],value[i]=rd()*rd()%mod;
	for(int i=1;i<=n;i++) cin>>b[i][0]>>b[i][1]>>b[i][2];
	for(int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		ask[l].push_back(make_pair(r,i));
	}
	l=1;
	while(l<=n){
		while(r<=n&&valuea==valueb){
			r++;
			valuea=(valuea+Mod-Hash(val[a[r][0]][0]))%Mod;
			val[a[r][0]][0]=(value[r]+val[a[r][0]][0])%mod;
			valuea=(valuea+Hash(val[a[r][0]][0]))%Mod;
			valuea=(valuea+Mod-Hash(val[a[r][1]][0]))%Mod;
			val[a[r][1]][0]=(value[r]+val[a[r][1]][0])%mod;
			valuea=(valuea+Hash(val[a[r][1]][0]))%Mod;
			valuea=(valuea+Mod-Hash(val[a[r][2]][0]))%Mod;
			val[a[r][2]][0]=(value[r]+val[a[r][2]][0])%mod;
			valuea=(valuea+Hash(val[a[r][2]][0]))%Mod;
			valueb=(valueb+Mod-Hash(val[b[r][0]][1]))%Mod;
			val[b[r][0]][1]=(value[r]+val[b[r][0]][1])%mod;
			valueb=(valueb+Hash(val[b[r][0]][1]))%Mod;
			valueb=(valueb+Mod-Hash(val[b[r][1]][1]))%Mod;
			val[b[r][1]][1]=(value[r]+val[b[r][1]][1])%mod;
			valueb=(valueb+Hash(val[b[r][1]][1]))%Mod;
			valueb=(valueb+Mod-Hash(val[b[r][2]][1]))%Mod;
			val[b[r][2]][1]=(value[r]+val[b[r][2]][1])%mod;
			valueb=(valueb+Hash(val[b[r][2]][1]))%Mod;
		}
		R[l]=r;
		valuea=(valuea+Mod-Hash(val[a[l][0]][0]))%Mod;
		val[a[l][0]][0]=(val[a[l][0]][0]+mod-value[l])%mod;
		valuea=(valuea+Hash(val[a[l][0]][0]))%Mod;
		valuea=(valuea+Mod-Hash(val[a[l][1]][0]))%Mod;
		val[a[l][1]][0]=(val[a[l][1]][0]+mod-value[l])%mod;
		valuea=(valuea+Hash(val[a[l][1]][0]))%Mod;
		valuea=(valuea+Mod-Hash(val[a[l][2]][0]))%Mod;
		val[a[l][2]][0]=(val[a[l][2]][0]+mod-value[l])%mod;
		valuea=(valuea+Hash(val[a[l][2]][0]))%Mod;
		valueb=(valueb+Mod-Hash(val[b[l][0]][1]))%Mod;
		val[b[l][0]][1]=(val[b[l][0]][1]+mod-value[l])%mod;
		valueb=(valueb+Hash(val[b[l][0]][1]))%Mod;
		valueb=(valueb+Mod-Hash(val[b[l][1]][1]));
		val[b[l][1]][1]=(val[b[l][1]][1]+mod-value[l])%mod;
		valueb=(valueb+Hash(val[b[l][1]][1]))%Mod;
		valueb=(valueb+Mod-Hash(val[b[l][2]][1]))%Mod;
		val[b[l][2]][1]=(val[b[l][2]][1]+mod-value[l])%mod;
		valueb=(valueb+Hash(val[b[l][2]][1]))%Mod;
		l++;
	}
	for(int i=1;i<=n;i++){
		for(pair<int,int> now:ask[i]) answer[now.second]=(now.first<R[i]?"Yes":"No");
	}	
	for(int i=1;i<=q;i++) cout<<answer[i]<<'\n';
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

score: 5
Accepted
time: 6ms
memory: 44044kb

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 26ms
memory: 51236kb

Pretest #10:

score: 5
Accepted
time: 30ms
memory: 51048kb

Pretest #11:

score: 5
Accepted
time: 205ms
memory: 59576kb

Pretest #12:

score: 5
Accepted
time: 215ms
memory: 58748kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 150ms
memory: 69928kb

Pretest #16:

score: 5
Accepted
time: 145ms
memory: 69756kb

Pretest #17:

score: 5
Accepted
time: 20ms
memory: 47104kb

Pretest #18:

score: 5
Accepted
time: 14ms
memory: 48412kb

Pretest #19:

score: 5
Accepted
time: 441ms
memory: 78580kb

Pretest #20:

score: 5
Accepted
time: 491ms
memory: 87288kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

score: 5
Accepted
time: 7ms
memory: 46892kb

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 27ms
memory: 49912kb

Test #10:

score: 5
Accepted
time: 27ms
memory: 50948kb

Test #11:

score: 5
Accepted
time: 200ms
memory: 58620kb

Test #12:

score: 5
Accepted
time: 206ms
memory: 58736kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 149ms
memory: 69188kb

Test #16:

score: 5
Accepted
time: 137ms
memory: 69232kb

Test #17:

score: 5
Accepted
time: 24ms
memory: 46256kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 429ms
memory: 79484kb

Test #20:

score: 5
Accepted
time: 466ms
memory: 87528kb

Extra Test:

score: 0
Extra Test Passed