QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498684 | #9155. 集合 | cjwen | 100 ✓ | 151ms | 20852kb | C++14 | 2.6kb | 2024-07-30 17:47:19 | 2024-07-30 17:47:22 |
Judging History
answer
#include<bits/stdc++.h>
#define mo(x, y) ((((x)%P##y)+P##y)%P##y)
#define qmi2(x) (pb3[x/L]*pb2[x%L]%P2)
using namespace std;
void read(int &x){
x = 0;
char c = getchar();
while(c < '0'|| c > '9') c = getchar();
while('0' <= c && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
}
long long qmi(long long qa, long long qb, long long qc){
long long qans = 1;
while(qb){
if(qb & 1) qans = qans * qa % qc;
qa = qa * qa % qc;
qb >>= 1;
}
return qans;
}
const int N = 2e5 + 5, M = 6e5 + 5, Q = 1e6 + 5;
const int B1 = 131, P1 = 998244353;
const int B2 = 13331, P2 = 1e9+7;
const int L = 5e4;
int n, m, q;
int a[N][3];
int b[N][3];
int maxl[N];
long long pha[M], phb[M];
long long hsha, hshb;
long long pb1[N];
long long pb2[L], pb3[L];
void add(int x){
for(int i = 0; i < 3; i++){
hsha = mo(hsha-qmi2(pha[a[x][i]]), 2);
pha[a[x][i]] = mo(pha[a[x][i]]+pb1[x], 1);
hsha = mo(hsha+qmi2(pha[a[x][i]]), 2);
hshb = mo(hshb-qmi2(phb[b[x][i]]), 2);
phb[b[x][i]] = mo(phb[b[x][i]]+pb1[x], 1);
hshb = mo(hshb+qmi2(phb[b[x][i]]), 2);
}
}
void del(int x){
for(int i = 0; i < 3; i++){
hsha = mo(hsha-qmi2(pha[a[x][i]]), 2);
pha[a[x][i]] = mo(pha[a[x][i]]-pb1[x], 1);
hsha = mo(hsha+qmi2(pha[a[x][i]]), 2);
hshb = mo(hshb-qmi2(phb[b[x][i]]), 2);
phb[b[x][i]] = mo(phb[b[x][i]]-pb1[x], 1);
hshb = mo(hshb+qmi2(phb[b[x][i]]), 2);
}
}
bool check(){
return hsha == hshb;
}
int main(){
pb1[0] = 1;
for(int i = 1; i < N; i++){
pb1[i] = pb1[i-1] * B1 % P1;
}
pb2[0] = 1;
for(int i = 1; i < L; i++){
pb2[i] = pb2[i-1] * B2 % P2;
}
pb3[0] = 1; pb3[1] = pb2[L-1] * B2 % P2;
for(int i = 1; i < L; i++){
pb3[i] = pb3[i-1] * pb3[1] % P2;
}
read(n); read(m); read(q);
for(int i = 1; i <= n; i++){
read(a[i][0]); read(a[i][1]); read(a[i][2]);
}
for(int i = 1; i <= n; i++){
read(b[i][0]); read(b[i][1]); read(b[i][2]);
}
hsha = hshb = m;
for(int l = 1, r = 0; l <= n; ){
while(r < n){
add(++r);
if(!check()){
del(r--);
break;
}
}
maxl[l] = r;
del(l++);
}
int x = 0, y = 0;
while(q--){
read(x); read(y);
if(y <= maxl[x]){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 3ms
memory: 14004kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 13888kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 13664kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 13816kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 10700kb
Pretest #6:
score: 5
Accepted
time: 3ms
memory: 13432kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 13568kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 10632kb
Pretest #9:
score: 5
Accepted
time: 7ms
memory: 13344kb
Pretest #10:
score: 5
Accepted
time: 11ms
memory: 11060kb
Pretest #11:
score: 5
Accepted
time: 82ms
memory: 12684kb
Pretest #12:
score: 5
Accepted
time: 85ms
memory: 12692kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 10916kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 14032kb
Pretest #15:
score: 5
Accepted
time: 41ms
memory: 11124kb
Pretest #16:
score: 5
Accepted
time: 51ms
memory: 13860kb
Pretest #17:
score: 5
Accepted
time: 11ms
memory: 10900kb
Pretest #18:
score: 5
Accepted
time: 12ms
memory: 11644kb
Pretest #19:
score: 5
Accepted
time: 131ms
memory: 12612kb
Pretest #20:
score: 5
Accepted
time: 137ms
memory: 20748kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 13400kb
Test #2:
score: 5
Accepted
time: 3ms
memory: 11108kb
Test #3:
score: 5
Accepted
time: 3ms
memory: 10572kb
Test #4:
score: 5
Accepted
time: 3ms
memory: 13356kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 13924kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 10920kb
Test #7:
score: 5
Accepted
time: 3ms
memory: 13720kb
Test #8:
score: 5
Accepted
time: 3ms
memory: 13412kb
Test #9:
score: 5
Accepted
time: 11ms
memory: 10468kb
Test #10:
score: 5
Accepted
time: 11ms
memory: 11052kb
Test #11:
score: 5
Accepted
time: 85ms
memory: 12672kb
Test #12:
score: 5
Accepted
time: 80ms
memory: 12624kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 10548kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 13552kb
Test #15:
score: 5
Accepted
time: 52ms
memory: 13908kb
Test #16:
score: 5
Accepted
time: 41ms
memory: 14028kb
Test #17:
score: 5
Accepted
time: 11ms
memory: 11012kb
Test #18:
score: 5
Accepted
time: 12ms
memory: 14148kb
Test #19:
score: 5
Accepted
time: 143ms
memory: 12576kb
Test #20:
score: 5
Accepted
time: 151ms
memory: 20852kb
Extra Test:
score: 0
Extra Test Passed