QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490096#9155. 集合Snowfall1462#100 ✓1059ms261692kbC++143.0kb2024-07-25 11:14:072024-07-25 11:14:07

Judging History

你现在查看的是最新测评结果

  • [2024-07-25 11:14:07]
  • 评测
  • 测评结果:100
  • 用时:1059ms
  • 内存:261692kb
  • [2024-07-25 11:14:07]
  • 提交

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