QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#506286 | #9155. 集合 | Sheez_Official | 100 ✓ | 235ms | 19320kb | C++14 | 1.1kb | 2024-08-05 16:27:05 | 2024-08-05 16:27:05 |
Judging History
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