QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537295#9155. 集合shiomusubi496#100 ✓199ms19696kbC++172.0kb2024-08-30 09:23:402024-08-30 09:23:41

Judging History

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

  • [2024-08-30 09:23:41]
  • 评测
  • 测评结果:100
  • 用时:199ms
  • 内存:19696kb
  • [2024-08-30 09:23:40]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;
using ull = unsigned long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

constexpr ll inf = 1001001001001001001;

mt19937_64 mt(random_device{}());

int main() {
    int N, M, Q; scanf("%d%d%d", &N, &M, &Q);
    vector<array<int, 3>> A(N), B(N);
    rep (i, N) rep (j, 3) scanf("%d", &A[i][j]), --A[i][j];
    rep (i, N) rep (j, 3) scanf("%d", &B[i][j]), --B[i][j];
    vector<ull> X(N);
    rep (i, N) X[i] = mt();
    vector<int> R(N);
    int cur = 0;
    vector<ull> YA(M), YB(M);
    ull ZA = 0, ZB = 0;
    auto check = [&] {
        ull nxt_za = ZA, nxt_zb = ZB;
        rep (i, 3) nxt_za += (YA[A[cur][i]] ^ X[cur]) - YA[A[cur][i]];
        rep (i, 3) nxt_zb += (YB[B[cur][i]] ^ X[cur]) - YB[B[cur][i]];
        return nxt_za == nxt_zb;
    };
    rep (l, N) {
        while (cur < N && check()) {
            rep (i, 3) ZA += (YA[A[cur][i]] ^ X[cur]) - YA[A[cur][i]];
            rep (i, 3) ZB += (YB[B[cur][i]] ^ X[cur]) - YB[B[cur][i]];
            rep (i, 3) YA[A[cur][i]] ^= X[cur];
            rep (i, 3) YB[B[cur][i]] ^= X[cur];
            ++cur;
        }
        R[l] = cur;
        rep (i, 3) ZA += (YA[A[l][i]] ^ X[l]) - YA[A[l][i]];
        rep (i, 3) ZB += (YB[B[l][i]] ^ X[l]) - YB[B[l][i]];
        rep (i, 3) YA[A[l][i]] ^= X[l];
        rep (i, 3) YB[B[l][i]] ^= X[l];
    }
    rep (_, Q) {
        int l, r; scanf("%d%d", &l, &r);
        --l;
        puts(R[l] >= r ? "Yes" : "No");
    }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 20ms
memory: 3760kb

Pretest #10:

score: 5
Accepted
time: 20ms
memory: 3712kb

Pretest #11:

score: 5
Accepted
time: 78ms
memory: 10344kb

Pretest #12:

score: 5
Accepted
time: 78ms
memory: 10264kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 99ms
memory: 3688kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 8ms
memory: 4916kb

Pretest #19:

score: 5
Accepted
time: 182ms
memory: 10244kb

Pretest #20:

score: 5
Accepted
time: 199ms
memory: 19616kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 17ms
memory: 3644kb

Test #10:

score: 5
Accepted
time: 20ms
memory: 3960kb

Test #11:

score: 5
Accepted
time: 78ms
memory: 10440kb

Test #12:

score: 5
Accepted
time: 77ms
memory: 10244kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 105ms
memory: 3760kb

Test #16:

score: 5
Accepted
time: 102ms
memory: 3788kb

Test #17:

score: 5
Accepted
time: 7ms
memory: 3892kb

Test #18:

score: 5
Accepted
time: 8ms
memory: 4980kb

Test #19:

score: 5
Accepted
time: 184ms
memory: 10340kb

Test #20:

score: 5
Accepted
time: 189ms
memory: 19696kb

Extra Test:

score: 0
Extra Test Passed