QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560981 | #9155. 集合 | oyzr | 100 ✓ | 600ms | 29564kb | C++23 | 2.1kb | 2024-09-12 19:17:56 | 2024-09-12 19:17:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXM = 6e5 + 5, MAXQ = 1e6 + 5, MOD = 998244353;
int read(){
char c = getchar();
while (c > '9' || c < '0')
c = getchar();
int res = 0;
while (c >= '0' && c <= '9'){
res = (res << 3) + (res << 1) + (c ^ 48);
c = getchar();
}
return res;
}
long long qpow(long long a, long long b){
long long res = 1;
for (; b; b >>= 1, a = a * a % MOD)
if (b & 1)
res = res * a % MOD;
return res;
}
long long base, p;
int a[MAXN][3], b[MAXN][3];
long long ha[MAXM], hb[MAXM];
long long bp[MAXN], olda[MAXM], oldb[MAXM];
long long numa = 0, numb = 0;
int cnt = 0;
void insert(int id, int k){
cnt++;
for (int i = 0; i < 3; i++){
int x = a[id][i];
numa -= olda[x];
ha[x] += bp[id] * k; ha[x] = (ha[x] + MOD) % MOD;
olda[x] = qpow(p, ha[x]);
numa += olda[x]; numa = (numa % MOD + MOD) % MOD;
}
for (int i = 0; i < 3; i++){
int x = b[id][i];
numb -= oldb[x];
hb[x] += bp[id] * k; hb[x] = (hb[x] + MOD) % MOD;
oldb[x] = qpow(p, hb[x]);
numb += oldb[x]; numb = (numb % MOD + MOD) % MOD;
}
}
int ans[MAXN];
mt19937 rnd(time(0));
int main(){
base = rnd() % MOD, p = rnd() % MOD;
int n = read(), m = read(), q = read();
bp[0] = 1;
for (int i = 1; i <= n; i++)
bp[i] = bp[i - 1] * base % MOD;
for (int i = 1; i <= m; i++)
olda[i] = oldb[i] = 1;
for (int i = 1; i <= n; i++)
a[i][0] = read(), a[i][1] = read(), a[i][2] = read();
for (int i = 1; i <= n; i++)
b[i][0] = read(), b[i][1] = read(), b[i][2] = read();
int r = 0;
for (int l = 1; l <= n; l++){
while (numa == numb && r < n){
r++;
insert(r, 1);
}
ans[l] = r - (numa != numb);
insert(l, -1);
}
while (q--){
int l = read(), r = read();
if (r <= ans[l])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 12056kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11912kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 13956kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 14012kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 13952kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 11844kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 13896kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 11912kb
Pretest #9:
score: 5
Accepted
time: 51ms
memory: 13956kb
Pretest #10:
score: 5
Accepted
time: 31ms
memory: 14036kb
Pretest #11:
score: 5
Accepted
time: 362ms
memory: 14400kb
Pretest #12:
score: 5
Accepted
time: 380ms
memory: 16844kb
Pretest #13:
score: 5
Accepted
time: 6ms
memory: 11908kb
Pretest #14:
score: 5
Accepted
time: 6ms
memory: 14040kb
Pretest #15:
score: 5
Accepted
time: 244ms
memory: 13976kb
Pretest #16:
score: 5
Accepted
time: 239ms
memory: 12060kb
Pretest #17:
score: 5
Accepted
time: 34ms
memory: 16120kb
Pretest #18:
score: 5
Accepted
time: 26ms
memory: 16440kb
Pretest #19:
score: 5
Accepted
time: 600ms
memory: 16896kb
Pretest #20:
score: 5
Accepted
time: 509ms
memory: 29432kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 11972kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 14020kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 13956kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 14060kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 13896kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 12060kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 11968kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 11916kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 11976kb
Test #10:
score: 5
Accepted
time: 59ms
memory: 13956kb
Test #11:
score: 5
Accepted
time: 382ms
memory: 17080kb
Test #12:
score: 5
Accepted
time: 347ms
memory: 17276kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 16168kb
Test #14:
score: 5
Accepted
time: 5ms
memory: 11996kb
Test #15:
score: 5
Accepted
time: 223ms
memory: 11924kb
Test #16:
score: 5
Accepted
time: 215ms
memory: 13980kb
Test #17:
score: 5
Accepted
time: 30ms
memory: 11928kb
Test #18:
score: 5
Accepted
time: 28ms
memory: 17180kb
Test #19:
score: 5
Accepted
time: 540ms
memory: 16504kb
Test #20:
score: 5
Accepted
time: 516ms
memory: 29564kb
Extra Test:
score: 0
Extra Test Passed