QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487923#9155. 集合PinkRabbit100 ✓439ms58748kbC++202.1kb2024-07-23 12:57:102024-07-23 12:57:12

Judging History

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

  • [2024-07-23 12:57:12]
  • 评测
  • 测评结果:100
  • 用时:439ms
  • 内存:58748kb
  • [2024-07-23 12:57:10]
  • 提交

answer

#include <iostream>

#define PKRBT
//#undef PKRBT
#ifdef PKRBT
using std::cin;
using std::cout;
#else
#include <fstream>
std::ifstream cin("set.in");
std::ofstream cout("set.out");
#endif

#include <vector>
#include <array>
#include <random>
#include <unordered_map>
using std::vector;
#define F(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define F2(i, n) F(i, 0, (int)(n) - 1)

// ==========================================

int main() {
#ifdef PKRBT
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    constexpr int K = 3;
    int n, m, q;
    cin >> n >> m >> q;
    vector<std::array<int, 3>> A(n), B(n);
    F2(i, n)
        F2(k, K)
            cin >> A[i][k],
            --A[i][k];
    F2(i, n)
        F2(k, K)
            cin >> B[i][k],
            --B[i][k];
    vector<int> lb(n); {
        using ULL = unsigned long long;
        vector<ULL> W(n); {
            std::mt19937_64 rng(0x20240718llu);
            F2(i, n)
                W[i] = rng();
        }
        vector<ULL> hash_A(m, 0), hash_B(m, 0);
        std::unordered_map<ULL, int> buk;
        int cnt = 0;
        auto modify = [&](ULL val, int c) {
            if (buk[val])
                --cnt;
            buk[val] += c;
            if (buk[val])
                ++cnt;
        };
        auto f = [&](int i, int c) {
            F2(k, K) {
                ULL &vA = hash_A[A[i][k]];
                modify(vA, -1);
                vA += c * W[i];
                modify(vA, 1);
            }
            F2(k, K) {
                ULL &vB = hash_B[B[i][k]];
                modify(vB, 1);
                vB += c * W[i];
                modify(vB, -1);
            }
        };
        int j = 0;
        F2(i, n) {
            f(i, 1);
            while (cnt)
                f(j++, -1);
            lb[i] = j;
        }
    }
    F2(q_, q) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << (l >= lb[r] ? "Yes\n" : "No\n");
    }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 289ms
memory: 55328kb

Pretest #12:

score: 5
Accepted
time: 266ms
memory: 52804kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 95ms
memory: 4084kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 361ms
memory: 53640kb

Pretest #20:

score: 5
Accepted
time: 393ms
memory: 58592kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 268ms
memory: 53084kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 100ms
memory: 4288kb

Test #17:

score: 5
Accepted
time: 26ms
memory: 8596kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 439ms
memory: 52636kb

Test #20:

score: 5
Accepted
time: 401ms
memory: 58748kb

Extra Test:

score: 0
Extra Test Passed