QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492977#9155. 集合A_programmer100 ✓636ms20056kbC++171.5kb2024-07-26 17:52:092024-07-26 17:52:10

Judging History

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

  • [2024-07-26 17:52:10]
  • 评测
  • 测评结果:100
  • 用时:636ms
  • 内存:20056kb
  • [2024-07-26 17:52:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull B1 = 23333333;
const ull B2 = 19260817;
const ull mod = 998244353;
const int maxn = 2e5 + 5;
const int maxm = 6e5 + 5;

int A[maxn][3], B[maxn][3];
int rpos[maxn];

ull hsh[maxm][2], mi[maxn], Ha, Hb;
ull fpow(ull a, ull b)
{
    ull ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a;
        a = a * a; b >>= 1;
    }
    return ans;
}

void add(int pos, int op)
{
    for (int i = 0; i < 3; i++)
    {
        Ha -= fpow(B2, hsh[A[pos][i]][0]);
        (hsh[A[pos][i]][0] += (op ? mi[pos] : mod - mi[pos])) %= mod;
        Ha += fpow(B2, hsh[A[pos][i]][0]);

        Hb -= fpow(B2, hsh[B[pos][i]][1]);
        (hsh[B[pos][i]][1] += (op ? mi[pos] : mod - mi[pos])) %= mod;
        Hb += fpow(B2, hsh[B[pos][i]][1]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;
    mi[0] = 1; for (int i = 1; i <= n; i++) mi[i] = mi[i - 1] * B1 % mod;
    for (int i = 1; i <= n; i++) cin >> A[i][0] >> A[i][1] >> A[i][2];
    for (int i = 1; i <= n; i++) cin >> B[i][0] >> B[i][1] >> B[i][2];

    int pos = 1; add(1, 1);
    for (int i = 1; i <= n; i++)
    {
        while (pos < n && Ha == Hb) add(++pos, 1);
        if (pos == n && Ha == Hb) rpos[i] = n + 1; else rpos[i] = pos; add(i, 0);
    }
    while (q--)
    {
        int l, r; cin >> l >> r;
        cout << (r >= rpos[l] ? "No" : "Yes") << "\n";
    }
    return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 1ms
memory: 7788kb

Pretest #2:

score: 5
Accepted
time: 1ms
memory: 7724kb

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 9856kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 9776kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 9776kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 7672kb

Pretest #7:

score: 5
Accepted
time: 1ms
memory: 9732kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 9776kb

Pretest #9:

score: 5
Accepted
time: 22ms
memory: 9732kb

Pretest #10:

score: 5
Accepted
time: 23ms
memory: 7720kb

Pretest #11:

score: 5
Accepted
time: 524ms
memory: 11768kb

Pretest #12:

score: 5
Accepted
time: 519ms
memory: 13952kb

Pretest #13:

score: 5
Accepted
time: 6ms
memory: 9792kb

Pretest #14:

score: 5
Accepted
time: 3ms
memory: 9808kb

Pretest #15:

score: 5
Accepted
time: 113ms
memory: 7740kb

Pretest #16:

score: 5
Accepted
time: 115ms
memory: 9800kb

Pretest #17:

score: 5
Accepted
time: 54ms
memory: 7908kb

Pretest #18:

score: 5
Accepted
time: 46ms
memory: 10876kb

Pretest #19:

score: 5
Accepted
time: 636ms
memory: 13884kb

Pretest #20:

score: 5
Accepted
time: 621ms
memory: 20056kb

Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 7676kb

Test #2:

score: 5
Accepted
time: 1ms
memory: 7724kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 7712kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 9776kb

Test #5:

score: 5
Accepted
time: 0ms
memory: 9704kb

Test #6:

score: 5
Accepted
time: 0ms
memory: 7712kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 9792kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 9712kb

Test #9:

score: 5
Accepted
time: 23ms
memory: 7812kb

Test #10:

score: 5
Accepted
time: 14ms
memory: 7724kb

Test #11:

score: 5
Accepted
time: 519ms
memory: 11864kb

Test #12:

score: 5
Accepted
time: 511ms
memory: 13968kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 9792kb

Test #14:

score: 5
Accepted
time: 6ms
memory: 7840kb

Test #15:

score: 5
Accepted
time: 111ms
memory: 7804kb

Test #16:

score: 5
Accepted
time: 113ms
memory: 7924kb

Test #17:

score: 5
Accepted
time: 54ms
memory: 9924kb

Test #18:

score: 5
Accepted
time: 46ms
memory: 10824kb

Test #19:

score: 5
Accepted
time: 636ms
memory: 11832kb

Test #20:

score: 5
Accepted
time: 625ms
memory: 19960kb

Extra Test:

score: 0
Extra Test Passed