QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490096 | #9155. 集合 | Snowfall1462# | 100 ✓ | 1059ms | 261692kb | C++14 | 3.0kb | 2024-07-25 11:14:07 | 2024-07-25 11:14:07 |
Judging History
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
constexpr int N = 200010, M = 600010, mod = 998244353;
int n, m, Q, maxr[N];
ll pt[N], Hash1[M], Hash2[M];
struct Node
{
int a, b, c;
Node() : a(0), b(0), c(0) {}
Node(int a_, int b_, int c_) : a(a_), b(b_), c(c_) {}
} A[N], B[N], tmp[N];
gp_hash_table<ll, int> f, g;
int main()
{
cin >> n >> m >> Q;
pt[0] = 1;
for (int i = 1; i <= n; i++)
pt[i] = 131 * pt[i - 1] % mod;
for (int i = 1; i <= n; i++)
cin >> A[i].a >> A[i].b >> A[i].c;
for (int i = 1; i <= n; i++)
cin >> B[i].a >> B[i].b >> B[i].c;
for (int l = 1; l <= n; l++)
{
for (int r = maxr[l - 1] + 1; r <= n; r++)
{
ll Alsta = Hash1[A[r].a], Alstb = Hash1[A[r].b], Alstc = Hash1[A[r].c], Ana, Anb, Anc;
Ana = Hash1[A[r].a] = (Alsta + pt[r]) % mod;
Anb = Hash1[A[r].b] = (Alstb + pt[r]) % mod;
Anc = Hash1[A[r].c] = (Alstc + pt[r]) % mod;
--f[Alsta], --f[Alstb], --f[Alstc];
++f[Ana], ++f[Anb], ++f[Anc];
ll Blsta = Hash2[B[r].a], Blstb = Hash2[B[r].b], Blstc = Hash2[B[r].c], Bna, Bnb, Bnc;
Bna = Hash2[B[r].a] = (Blsta + pt[r]) % mod;
Bnb = Hash2[B[r].b] = (Blstb + pt[r]) % mod;
Bnc = Hash2[B[r].c] = (Blstc + pt[r]) % mod;
--g[Blsta], --g[Blstb], --g[Blstc];
++g[Bna], ++g[Bnb], ++g[Bnc];
if (f[Alsta] != g[Alsta] || f[Alstb] != g[Alstb] || f[Alstc] != g[Alstc] || f[Ana] != g[Ana] || f[Anb] != g[Anb] || f[Anc] != g[Anc])
{
++f[Alsta], ++f[Alstb], ++f[Alstc];
--f[Ana], --f[Anb], --f[Anc];
++g[Blsta], ++g[Blstb], ++g[Blstc];
--g[Bna], --g[Bnb], --g[Bnc];
Hash1[A[r].a] = Alsta, Hash1[A[r].b] = Alstb, Hash1[A[r].c] = Alstc;
Hash2[B[r].a] = Blsta, Hash2[B[r].b] = Blstb, Hash2[B[r].c] = Blstc;
break;
}
maxr[l] = r;
}
maxr[l + 1] = maxr[l];
ll Alsta = Hash1[A[l].a], Alstb = Hash1[A[l].b], Alstc = Hash1[A[l].c], Ana, Anb, Anc;
Ana = Hash1[A[l].a] = ((Alsta - pt[l]) % mod + mod) % mod;
Anb = Hash1[A[l].b] = ((Alstb - pt[l]) % mod + mod) % mod;
Anc = Hash1[A[l].c] = ((Alstc - pt[l]) % mod + mod) % mod;
--f[Alsta], --f[Alstb], --f[Alstc];
++f[Ana], ++f[Anb], ++f[Anc];
ll Blsta = Hash2[B[l].a], Blstb = Hash2[B[l].b], Blstc = Hash2[B[l].c], Bna, Bnb, Bnc;
Bna = Hash2[B[l].a] = ((Blsta - pt[l]) % mod + mod) % mod;
Bnb = Hash2[B[l].b] = ((Blstb - pt[l]) % mod + mod) % mod;
Bnc = Hash2[B[l].c] = ((Blstc - pt[l]) % mod + mod) % mod;
--g[Blsta], --g[Blstb], --g[Blstc];
++g[Bna], ++g[Bnb], ++g[Bnc];
}
while (Q--)
{
int l, r;
cin >> l >> r;
cout << (maxr[l] >= r ? "Yes" : "No") << endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 14008kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 13540kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 13000kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 14512kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 13000kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 14132kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 13380kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 14648kb
Pretest #9:
score: 5
Accepted
time: 84ms
memory: 13784kb
Pretest #10:
score: 5
Accepted
time: 100ms
memory: 13072kb
Pretest #11:
score: 5
Accepted
time: 470ms
memory: 261692kb
Pretest #12:
score: 5
Accepted
time: 442ms
memory: 136500kb
Pretest #13:
score: 5
Accepted
time: 8ms
memory: 16208kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 14884kb
Pretest #15:
score: 5
Accepted
time: 531ms
memory: 14984kb
Pretest #16:
score: 5
Accepted
time: 531ms
memory: 14692kb
Pretest #17:
score: 5
Accepted
time: 32ms
memory: 29552kb
Pretest #18:
score: 5
Accepted
time: 37ms
memory: 29800kb
Pretest #19:
score: 5
Accepted
time: 935ms
memory: 210488kb
Pretest #20:
score: 5
Accepted
time: 1059ms
memory: 144908kb
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 14492kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 14636kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 13864kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 14340kb
Test #5:
score: 5
Accepted
time: 2ms
memory: 12944kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 12996kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 14060kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 14812kb
Test #9:
score: 5
Accepted
time: 91ms
memory: 14248kb
Test #10:
score: 5
Accepted
time: 64ms
memory: 14336kb
Test #11:
score: 5
Accepted
time: 470ms
memory: 210564kb
Test #12:
score: 5
Accepted
time: 403ms
memory: 138644kb
Test #13:
score: 5
Accepted
time: 8ms
memory: 16296kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 14428kb
Test #15:
score: 5
Accepted
time: 503ms
memory: 14664kb
Test #16:
score: 5
Accepted
time: 520ms
memory: 15512kb
Test #17:
score: 5
Accepted
time: 38ms
memory: 29132kb
Test #18:
score: 5
Accepted
time: 37ms
memory: 29948kb
Test #19:
score: 5
Accepted
time: 959ms
memory: 136620kb
Test #20:
score: 5
Accepted
time: 1018ms
memory: 144796kb
Extra Test:
score: 0
Extra Test Passed