QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491262#9155. 集合xinyue#100 ✓841ms87448kbC++1411.0kb2024-07-25 18:11:212024-07-25 18:11:21

Judging History

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

  • [2024-07-25 18:11:21]
  • 评测
  • 测评结果：100
  • 用时：841ms
  • 内存：87448kb
查看
  • [2024-07-25 18:11:21]
  • 提交

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++;
	}
	mod=1000000007;
	Mod=1e15+7;
	for(int i=1;i<=n;i++) value[i]=rd()*rd()%mod;
	C1=rd(),C2=rd(),C3=rd();
	r=0,l=1;
	valuea=valueb=0;
	for(int i=1;i<=m;i++) val[i][0]=val[i][1]=0;
	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++;
	}
	mod=1145141;
	Mod=1e17+7;
	for(int i=1;i<=n;i++) value[i]=rd()*rd()%mod;
	C1=rd(),C2=rd(),C3=rd();
	r=0,l=1;
	valuea=valueb=0;
	for(int i=1;i<=m;i++) val[i][0]=val[i][1]=0;
	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++;
	}
	mod=1919817;
	Mod=1e13+7;
	for(int i=1;i<=n;i++) value[i]=rd()*rd()%mod;
	C1=rd(),C2=rd(),C3=rd();
	r=0,l=1;
	valuea=valueb=0;
	for(int i=1;i<=m;i++) val[i][0]=val[i][1]=0;
	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++;
	}
	mod=104857601;
	Mod=1e18+17;
	for(int i=1;i<=n;i++) value[i]=rd()*rd()%mod;
	C1=rd(),C2=rd(),C3=rd();
	r=0,l=1;
	valuea=valueb=0;
	for(int i=1;i<=m;i++) val[i][0]=val[i][1]=0;
	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;
}
源文件, 语言: C++14

详细


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 25ms
memory: 47980kb

Pretest #11:

score: 5
Accepted
time: 605ms
memory: 58604kb

Pretest #12:

score: 5
Accepted
time: 588ms
memory: 59204kb

Pretest #13:

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

Pretest #14:

score: 5
Accepted
time: 15ms
memory: 47052kb

Pretest #15:

score: 5
Accepted
time: 148ms
memory: 69848kb

Pretest #16:

score: 5
Accepted
time: 141ms
memory: 66300kb

Pretest #17:

score: 5
Accepted
time: 63ms
memory: 48908kb

Pretest #18:

score: 5
Accepted
time: 60ms
memory: 49752kb

Pretest #19:

score: 5
Accepted
time: 803ms
memory: 79792kb

Pretest #20:

score: 5
Accepted
time: 831ms
memory: 87388kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

score: 5
Accepted
time: 5ms
memory: 46768kb

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 23ms
memory: 50856kb

Test #10:

score: 5
Accepted
time: 34ms
memory: 50988kb

Test #11:

score: 5
Accepted
time: 595ms
memory: 58664kb

Test #12:

score: 5
Accepted
time: 602ms
memory: 57908kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 151ms
memory: 69676kb

Test #16:

score: 5
Accepted
time: 125ms
memory: 69848kb

Test #17:

score: 5
Accepted
time: 60ms
memory: 48836kb

Test #18:

score: 5
Accepted
time: 61ms
memory: 48368kb

Test #19:

score: 5
Accepted
time: 806ms
memory: 79768kb

Test #20:

score: 5
Accepted
time: 841ms
memory: 87448kb

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-05 09:14:22 | 开源项目