QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492921 | #9155. 集合 | dengziyue | 100 ✓ | 746ms | 37588kb | C++14 | 2.4kb | 2024-07-26 17:14:11 | 2024-07-26 17:14:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define max_n 600000
#define mod 998244353ll
mt19937 rnd(998244353);
long long ba[max_n+2];
int n;
int m;
int q;
int a[max_n+2][3];
int b[max_n+2][3];
long long cnta1[max_n+2];
long long cntb1[max_n+2];
long long cnta2[max_n+2];
long long cntb2[max_n+2];
long long suma1=1,sumb1=1,suma2=1,sumb2=1;
int pos[max_n+2];
inline long long askrnd(){
return (1ll*(rnd()%1000000ll)*1000000ll+(rnd()%1000000ll))%998244352ll+1;
}
inline long long qp(long long a,long long b){
long long res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod; b>>=1;
}
return res;
}
inline void adda(int x,int y){
suma1=suma1*qp(cnta1[x],mod-2)%mod;
cnta1[x]=(cnta1[x]+ba[y])%mod;
suma1=suma1*cnta1[x]%mod;
suma2=suma2*qp(cnta2[x],mod-2)%mod;
cnta2[x]=(cnta2[x]+ba[y+n])%mod;
suma2=suma2*cnta2[x]%mod;
}
inline void addb(int x,int y){
sumb1=sumb1*qp(cntb1[x],mod-2)%mod;
cntb1[x]=(cntb1[x]+ba[y])%mod;
sumb1=sumb1*cntb1[x]%mod;
sumb2=sumb2*qp(cntb2[x],mod-2)%mod;
cntb2[x]=(cntb2[x]+ba[y+n])%mod;
sumb2=sumb2*cntb2[x]%mod;
}
inline void dela(int x,int y){
suma1=suma1*qp(cnta1[x],mod-2)%mod;
cnta1[x]=(cnta1[x]-ba[y]+mod)%mod;
suma1=suma1*cnta1[x]%mod;
suma2=suma2*qp(cnta2[x],mod-2)%mod;
cnta2[x]=(cnta2[x]-ba[y+n]+mod)%mod;
suma2=suma2*cnta2[x]%mod;
}
inline void delb(int x,int y){
sumb1=sumb1*qp(cntb1[x],mod-2)%mod;
cntb1[x]=(cntb1[x]-ba[y]+mod)%mod;
sumb1=sumb1*cntb1[x]%mod;
sumb2=sumb2*qp(cntb2[x],mod-2)%mod;
cntb2[x]=(cntb2[x]-ba[y+n]+mod)%mod;
sumb2=sumb2*cntb2[x]%mod;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("P10785_1.in","r",stdin);
freopen("P10785_1.out","w",stdout);
#endif
for(int i=1;i<=max_n;++i)ba[i]=askrnd();
unique(ba+1,ba+max_n+1);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i){
for(int j=0;j<=2;++j)scanf("%d",a[i]+j);
}
for(int i=1;i<=n;++i){
for(int j=0;j<=2;++j)scanf("%d",b[i]+j);
}
for(int i=1;i<=m;++i)cnta1[i]=cntb1[i]=cnta2[i]=cntb2[i]=1;
for(int i=1;i<=n;++i)pos[i]=i;
for(int l=1,r=0;l<=n;){
if(suma1==sumb1&&suma2==sumb2){
pos[l]=max(pos[l],r++);
if(r>n)break;
for(int j=0;j<=2;++j){adda(a[r][j],r); addb(b[r][j],r);}
}
else{
for(int j=0;j<=2;++j){dela(a[l][j],l); delb(b[l][j],l);}
++l;
}
}
for(int i=2;i<=n;++i)pos[i]=max(pos[i],pos[i-1]);
for(int ca=1,l,r;ca<=q;++ca){
scanf("%d%d",&l,&r);
if(pos[l]>=r)printf("Yes\n");
else printf("No\n");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 3ms
memory: 21636kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 22472kb
Pretest #3:
score: 5
Accepted
time: 5ms
memory: 22228kb
Pretest #4:
score: 5
Accepted
time: 7ms
memory: 22660kb
Pretest #5:
score: 5
Accepted
time: 3ms
memory: 22292kb
Pretest #6:
score: 5
Accepted
time: 7ms
memory: 21576kb
Pretest #7:
score: 5
Accepted
time: 8ms
memory: 21868kb
Pretest #8:
score: 5
Accepted
time: 4ms
memory: 21344kb
Pretest #9:
score: 5
Accepted
time: 23ms
memory: 21700kb
Pretest #10:
score: 5
Accepted
time: 26ms
memory: 21424kb
Pretest #11:
score: 5
Accepted
time: 614ms
memory: 29304kb
Pretest #12:
score: 5
Accepted
time: 614ms
memory: 26008kb
Pretest #13:
score: 5
Accepted
time: 14ms
memory: 22740kb
Pretest #14:
score: 5
Accepted
time: 10ms
memory: 25696kb
Pretest #15:
score: 5
Accepted
time: 129ms
memory: 20884kb
Pretest #16:
score: 5
Accepted
time: 118ms
memory: 22360kb
Pretest #17:
score: 5
Accepted
time: 59ms
memory: 21756kb
Pretest #18:
score: 5
Accepted
time: 58ms
memory: 23436kb
Pretest #19:
score: 5
Accepted
time: 733ms
memory: 28372kb
Pretest #20:
score: 5
Accepted
time: 746ms
memory: 36372kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 20936kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 20984kb
Test #3:
score: 5
Accepted
time: 4ms
memory: 21084kb
Test #4:
score: 5
Accepted
time: 7ms
memory: 21084kb
Test #5:
score: 5
Accepted
time: 8ms
memory: 22280kb
Test #6:
score: 5
Accepted
time: 4ms
memory: 21844kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 22200kb
Test #8:
score: 5
Accepted
time: 5ms
memory: 22068kb
Test #9:
score: 5
Accepted
time: 25ms
memory: 21048kb
Test #10:
score: 5
Accepted
time: 22ms
memory: 21428kb
Test #11:
score: 5
Accepted
time: 614ms
memory: 27124kb
Test #12:
score: 5
Accepted
time: 611ms
memory: 26856kb
Test #13:
score: 5
Accepted
time: 10ms
memory: 21048kb
Test #14:
score: 5
Accepted
time: 7ms
memory: 21008kb
Test #15:
score: 5
Accepted
time: 121ms
memory: 21668kb
Test #16:
score: 5
Accepted
time: 126ms
memory: 22632kb
Test #17:
score: 5
Accepted
time: 67ms
memory: 22184kb
Test #18:
score: 5
Accepted
time: 67ms
memory: 24612kb
Test #19:
score: 5
Accepted
time: 722ms
memory: 27348kb
Test #20:
score: 5
Accepted
time: 737ms
memory: 37588kb
Extra Test:
score: 0
Extra Test Passed