QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526400#9155. 集合bashkort#100 ✓1044ms68844kbC++202.3kb2024-08-21 15:23:312024-08-21 15:23:31

Judging History

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

  • [2024-08-21 15:23:31]
  • 评测
  • 测评结果:100
  • 用时:1044ms
  • 内存:68844kb
  • [2024-08-21 15:23:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

using ar = array<int, 3>;

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

    int n, m, q;
    cin >> n >> m >> q;

    vector<ar> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        for (auto &f : a[i]) {
            cin >> f;
            --f;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (auto &f : b[i]) {
            cin >> f;
            --f;
        }
    }

    struct Struct {
        vector<int> cnt;
        map<pair<int, int>, int> mp;

        void init(int k) {
            cnt.assign(k, 0);
        }

        void modify(ar a, ar b, int mod) {
            for (int &x : a) {
                cnt[x] += mod;
            }
            for (int x : a) {
                for (int y : b) {
                    mp[{x, y}] += mod;
                }
            }
        }

        int check(ar a, ar b) {
            ar adj{};
            for (int i = 0; i < 3; ++i) {
                int need = cnt[a[i]];
                for (int j = 0; j < 3; ++j) {
                    if (mp[{a[i], b[j]}] == need) {
                        adj[i] |= 1 << j;
                    }
                }
            }
            for (int mask = 1; mask < (1 << 3); ++mask) {
                int now = 0;
                for (int i = 0; i < 3; ++i) {
                    if (mask >> i & 1) {
                        now |= adj[i];
                    }
                }
                if (__builtin_popcount(mask) > __builtin_popcount(now)) {
                    return false;
                }
            }
            return true;
        }
    } A, B;
    A.init(m), B.init(m);

    vector<int> mxr(n + 1, n);
    for (int i = n - 1; i >= 0; --i) {
        mxr[i] = mxr[i + 1];
        A.modify(a[i], b[i], 1);
        B.modify(b[i], a[i], 1);
        while (mxr[i] > i && (!A.check(a[i], b[i]) || !B.check(b[i], a[i]))) {
            mxr[i] -= 1;
            A.modify(a[mxr[i]], b[mxr[i]], -1);
            B.modify(b[mxr[i]], a[mxr[i]], -1);
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        if (mxr[l] >= r) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 19ms
memory: 3632kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 195ms
memory: 8496kb

Pretest #12:

score: 5
Accepted
time: 230ms
memory: 8512kb

Pretest #13:

score: 5
Accepted
time: 4ms
memory: 3704kb

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 107ms
memory: 3592kb

Pretest #16:

score: 5
Accepted
time: 109ms
memory: 4180kb

Pretest #17:

score: 5
Accepted
time: 61ms
memory: 6076kb

Pretest #18:

score: 5
Accepted
time: 56ms
memory: 8880kb

Pretest #19:

score: 5
Accepted
time: 1044ms
memory: 39616kb

Pretest #20:

score: 5
Accepted
time: 987ms
memory: 68844kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 19ms
memory: 3576kb

Test #10:

score: 5
Accepted
time: 19ms
memory: 3504kb

Test #11:

score: 5
Accepted
time: 201ms
memory: 8568kb

Test #12:

score: 5
Accepted
time: 230ms
memory: 8460kb

Test #13:

score: 5
Accepted
time: 4ms
memory: 3636kb

Test #14:

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

Test #15:

score: 5
Accepted
time: 107ms
memory: 3896kb

Test #16:

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

Test #17:

score: 5
Accepted
time: 60ms
memory: 5908kb

Test #18:

score: 5
Accepted
time: 64ms
memory: 9392kb

Test #19:

score: 5
Accepted
time: 1021ms
memory: 35772kb

Test #20:

score: 5
Accepted
time: 1000ms
memory: 68240kb

Extra Test:

score: 0
Extra Test Passed