QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#496557 | #9155. 集合 | LiWenX# | 100 ✓ | 1013ms | 70932kb | C++20 | 3.4kb | 2024-07-28 13:10:14 | 2024-07-28 13:10:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
//#define int long long
#define mp make_pair
using namespace std;
int a[200005][3],b[200005][3];
int n,m,q;
struct Hash{
int val[200005],inv[200005],seed,mod;
int quickpow(int a,int b){
int ret=1;
while(b){
if(b&1) ret=1ll*ret*a%mod;
a=1ll*a*a%mod;
b>>=1;
}return ret;
}
int t[600005],ha;
void init(){
mt19937 rd(seed);
for(int i=1;i<=n;i++){
val[i]=rd()%mod;
inv[i]=quickpow(val[i],mod-2);
}
for(int i=1;i<=m;i++) t[i]=1;
}
int F(int x){
return (((1ll*x*911+113)%mod)^12786145)%mod;
}
void add(int x,int k){
ha-=F(t[k]);if(ha<0) ha+=mod;
t[k]=1ll*t[k]*val[x]%mod;
ha+=F(t[k]);if(ha>=mod) ha-=mod;
}
void del(int x,int k){
ha-=F(t[k]);if(ha<0) ha+=mod;
t[k]=1ll*t[k]*inv[x]%mod;
ha+=F(t[k]);if(ha>=mod) ha-=mod;
}
}A[5],B[5];
int ans[1000005];
vector<pair<int,int> > vec[200005];
signed main(){
// freopen("ex_4.in","r",stdin);
// freopen("solve.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
for(int i=1;i<=n;i++){
cin>>b[i][0]>>b[i][1]>>b[i][2];
}
A[0].mod=B[0].mod=998244353;
A[0].seed=B[0].seed=210;
A[0].init(),B[0].init();
A[1].mod=B[1].mod=1000000123;
A[1].seed=B[1].seed=123456789;
A[1].init(),B[1].init();
A[2].mod=B[2].mod=1000000007;
A[2].seed=B[2].seed=114;
A[2].init(),B[2].init();
A[3].mod=B[3].mod=1000000009;
A[3].seed=B[3].seed=514;
A[3].init(),B[3].init();
A[4].mod=B[4].mod=1145141;
A[4].seed=B[4].seed=1919;
A[4].init(),B[4].init();
for(int i=1;i<=q;i++){
int l,r;cin>>l>>r;
vec[l].push_back(mp(r,i));
}
int r=0;
for(int l=1;l<=n;l++){
while(r+1<=n){
r++;
for(int j=0;j<3;j++) A[0].add(r,a[r][j]);
for(int j=0;j<3;j++) B[0].add(r,b[r][j]);
for(int j=0;j<3;j++) A[1].add(r,a[r][j]);
for(int j=0;j<3;j++) B[1].add(r,b[r][j]);
for(int j=0;j<3;j++) A[2].add(r,a[r][j]);
for(int j=0;j<3;j++) B[2].add(r,b[r][j]);
for(int j=0;j<3;j++) A[3].add(r,a[r][j]);
for(int j=0;j<3;j++) B[3].add(r,b[r][j]);
for(int j=0;j<3;j++) A[4].add(r,a[r][j]);
for(int j=0;j<3;j++) B[4].add(r,b[r][j]);
if(A[0].ha==B[0].ha&&A[1].ha==B[1].ha&&A[2].ha==B[2].ha
&&A[3].ha==B[3].ha&&A[4].ha==B[4].ha){
continue;
}
for(int j=0;j<3;j++) A[0].del(r,a[r][j]);
for(int j=0;j<3;j++) B[0].del(r,b[r][j]);
for(int j=0;j<3;j++) A[1].del(r,a[r][j]);
for(int j=0;j<3;j++) B[1].del(r,b[r][j]);
for(int j=0;j<3;j++) A[2].del(r,a[r][j]);
for(int j=0;j<3;j++) B[2].del(r,b[r][j]);
for(int j=0;j<3;j++) A[3].del(r,a[r][j]);
for(int j=0;j<3;j++) B[3].del(r,b[r][j]);
for(int j=0;j<3;j++) A[4].del(r,a[r][j]);
for(int j=0;j<3;j++) B[4].del(r,b[r][j]);
r--;
break;
}
for(auto u:vec[l]){
ans[u.second]=(u.first<=r);
}
for(int j=0;j<3;j++) A[0].del(l,a[l][j]);
for(int j=0;j<3;j++) B[0].del(l,b[l][j]);
for(int j=0;j<3;j++) A[1].del(l,a[l][j]);
for(int j=0;j<3;j++) B[1].del(l,b[l][j]);
for(int j=0;j<3;j++) A[2].del(l,a[l][j]);
for(int j=0;j<3;j++) B[2].del(l,b[l][j]);
for(int j=0;j<3;j++) A[3].del(l,a[l][j]);
for(int j=0;j<3;j++) B[3].del(l,b[l][j]);
for(int j=0;j<3;j++) A[4].del(l,a[l][j]);
for(int j=0;j<3;j++) B[4].del(l,b[l][j]);
}
for(int i=1;i<=q;i++){
if(ans[i]) cout<<"Yes\n";
else cout<<"No\n";
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 48636kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 44524kb
Pretest #3:
score: 5
Accepted
time: 7ms
memory: 44596kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 46652kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 48700kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 46664kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 48760kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 46672kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 48560kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 46604kb
Pretest #11:
score: 5
Accepted
time: 828ms
memory: 53620kb
Pretest #12:
score: 5
Accepted
time: 832ms
memory: 55744kb
Pretest #13:
score: 5
Accepted
time: 11ms
memory: 46720kb
Pretest #14:
score: 5
Accepted
time: 11ms
memory: 46720kb
Pretest #15:
score: 5
Accepted
time: 117ms
memory: 60348kb
Pretest #16:
score: 5
Accepted
time: 117ms
memory: 58284kb
Pretest #17:
score: 5
Accepted
time: 84ms
memory: 44836kb
Pretest #18:
score: 5
Accepted
time: 76ms
memory: 48972kb
Pretest #19:
score: 5
Accepted
time: 994ms
memory: 66796kb
Pretest #20:
score: 5
Accepted
time: 1013ms
memory: 70932kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 44568kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 46644kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 46660kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 44616kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 46656kb
Test #6:
score: 5
Accepted
time: 3ms
memory: 46632kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 44592kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 44556kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 50596kb
Test #10:
score: 5
Accepted
time: 15ms
memory: 48512kb
Test #11:
score: 5
Accepted
time: 831ms
memory: 57260kb
Test #12:
score: 5
Accepted
time: 827ms
memory: 55640kb
Test #13:
score: 5
Accepted
time: 7ms
memory: 44672kb
Test #14:
score: 5
Accepted
time: 9ms
memory: 44688kb
Test #15:
score: 5
Accepted
time: 112ms
memory: 58440kb
Test #16:
score: 5
Accepted
time: 101ms
memory: 60440kb
Test #17:
score: 5
Accepted
time: 76ms
memory: 46904kb
Test #18:
score: 5
Accepted
time: 79ms
memory: 48932kb
Test #19:
score: 5
Accepted
time: 979ms
memory: 68824kb
Test #20:
score: 5
Accepted
time: 1009ms
memory: 70880kb
Extra Test:
score: 0
Extra Test Passed