QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#503630#9155. 集合zlxFTH100 ✓528ms82712kbC++171.7kb2024-08-03 21:22:322024-08-03 21:22:33

Judging History

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

  • [2024-08-03 21:22:33]
  • 评测
  • 测评结果:100
  • 用时:528ms
  • 内存:82712kb
  • [2024-08-03 21:22:32]
  • 提交

answer

#include <bits/stdc++.h>

using u64 = unsigned long long;

std::mt19937_64 rnd(std::random_device{}());

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::array<int, 3>> a(n), b(n);
    for (int i = 0; i < n; i++) {
        for (auto &v : a[i]) {
            std::cin >> v;
            v--;
        }
    }
    for (int i = 0; i < n; i++) {
        for (auto &v : b[i]) {
            std::cin >> v;
            v--;
        }
    }
    std::vector<int> ql(q), qr(q);
    std::vector c(n, std::vector<int>());
    for (int i = 0; i < q; i++) {
        std::cin >> ql[i] >> qr[i];
        ql[i]--, qr[i]--;
        c[qr[i]].emplace_back(i);
    }
    int bad = 0;
    std::unordered_map<u64, int> f;
    auto modify = [&](u64 key, int val) {
        if (f[key] != 0) {
            bad--;
        }
        f[key] += val;
        if (f[key] != 0) {
            bad++;
        }
    };
    std::vector<u64> ha(m), hb(m), d(n);
    auto add = [&](int p) {
        for (auto v : a[p]) {
            modify(ha[v], -1);
            ha[v] ^= d[p];
            modify(ha[v], 1);
        }
        for (auto v : b[p]) {
            modify(hb[v], 1);
            hb[v] ^= d[p];
            modify(hb[v], -1);
        }
    };
    std::vector<int> ans(q);
    int l = 0;
    for (int r = 0; r < n; r++) {
        d[r] = rnd();
        add(r);
        while (l <= r && bad) {
            add(l++);
        }
        for (auto i : c[r]) {
            if (ql[i] >= l) {
                ans[i] = 1;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        std::cout << (ans[i] ? "Yes" : "No") << "\n";
    }
    return 0;
}

详细


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 24ms
memory: 6724kb

Pretest #11:

score: 5
Accepted
time: 386ms
memory: 64748kb

Pretest #12:

score: 5
Accepted
time: 330ms
memory: 62300kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 521ms
memory: 77744kb

Pretest #20:

score: 5
Accepted
time: 528ms
memory: 82700kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 336ms
memory: 62608kb

Test #12:

score: 5
Accepted
time: 334ms
memory: 60580kb

Test #13:

score: 5
Accepted
time: 2ms
memory: 4072kb

Test #14:

score: 5
Accepted
time: 2ms
memory: 4132kb

Test #15:

score: 5
Accepted
time: 120ms
memory: 21424kb

Test #16:

score: 5
Accepted
time: 122ms
memory: 21308kb

Test #17:

score: 5
Accepted
time: 21ms
memory: 9080kb

Test #18:

score: 5
Accepted
time: 18ms
memory: 9968kb

Test #19:

score: 5
Accepted
time: 517ms
memory: 76676kb

Test #20:

score: 5
Accepted
time: 505ms
memory: 82712kb

Extra Test:

score: 0
Extra Test Passed