QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#535738#9155. 集合December456100 ✓296ms33232kbC++142.7kb2024-08-28 14:06:382024-08-28 14:06:39

Judging History

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

  • [2024-08-28 14:06:39]
  • 评测
  • 测评结果:100
  • 用时:296ms
  • 内存:33232kb
  • [2024-08-28 14:06:38]
  • 提交

answer

#include <cstdio>
#include <vector>

constexpr int MAXN = 200000 + 2;
constexpr int MAXM = MAXN * 3;
constexpr int MAXQ = MAXN * 5;
constexpr int HASH_P[2] = {1000000993, 1000000933};
constexpr int HASH_BASE[2] = {783763, 997991};
constexpr int SQRT_HASH_P = 31623;

template <int B, int P> class QuickPower {
public:
    int big[SQRT_HASH_P], small[SQRT_HASH_P];

    QuickPower() {
        big[0] = small[0] = 1;
        for (int i = 1; i < SQRT_HASH_P; i ++) {
            small[i] = (long long){small[i - 1]} * B % P;
        }
        for (int i = 1, b = small[SQRT_HASH_P - 1]; i < SQRT_HASH_P; i ++) {
            big[i] = (long long){big[i - 1]} * b % P;
        }
    }

    int operator ()(int x) const {
        return (long long){big[x / SQRT_HASH_P]} * small[x % SQRT_HASH_P] % P;
    }
};

template <int _type> class Hash {
public:
    static QuickPower<HASH_BASE[_type], HASH_P[_type]> pw;

    int val;

    template <int _t> Hash& operator +=(const Hash<_t> &rhs) {
        val = (val + pw(rhs.val)) % HASH_P[_type];
        return *this;
    }

    template <int _t> Hash& operator -=(const Hash<_t> &rhs) {
        val = (val + HASH_P[_type] - pw(rhs.val)) % HASH_P[_type];
        return *this;
    }

    bool operator !=(const Hash &rhs) {
        return val != rhs.val;
    }
};

template <int _type> QuickPower<HASH_BASE[_type], HASH_P[_type]> Hash<_type>::pw;

Hash<0> ph[MAXM][2];
Hash<1> th[2];

int a[MAXM], b[MAXM];
bool ans[MAXQ];

std::vector<std::pair<int, int>> qry[MAXN];

void remove(int v, int x, int o) {
    th[o] -= ph[v][o];
    ph[v][o] -= Hash<0>{x};
    th[o] += ph[v][o];
}

void insert(int v, int x, int o) {
    th[o] -= ph[v][o];
    ph[v][o] += Hash<0>{x};
    th[o] += ph[v][o];
}

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n * 3; i ++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n * 3; i ++) {
        scanf("%d", &b[i]);
    }
    for (int i = 0, l, r; i < q; i ++) {
        scanf("%d%d", &l, &r);
        qry[r].push_back({l, i});
    }

    for (int l = 1, r = 1; r <= n; r ++) {
        for (int i = 0; i < 3; i ++) {
            insert(a[r * 3 - i], r, 0);
            insert(b[r * 3 - i], r, 1);
        }

        while (th[0] != th[1]) {
            for (int i = 0; i < 3; i ++) {
                remove(a[l * 3 - i], l, 0);
                remove(b[l * 3 - i], l, 1);
            }
            l ++;
        }

        for (auto pr : qry[r]) {
            ans[pr.second] = pr.first >= l;
        }
    }

    for (int i = 0; i < q; i ++) {
        puts(ans[i] ? "Yes" : "No");
    }

    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 124ms
memory: 18248kb

Pretest #12:

score: 5
Accepted
time: 123ms
memory: 19880kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 117ms
memory: 24064kb

Pretest #16:

score: 5
Accepted
time: 119ms
memory: 22992kb

Pretest #17:

score: 5
Accepted
time: 9ms
memory: 14232kb

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 12612kb

Pretest #19:

score: 5
Accepted
time: 265ms
memory: 30344kb

Pretest #20:

score: 5
Accepted
time: 287ms
memory: 33168kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 108ms
memory: 19496kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 281ms
memory: 28952kb

Test #20:

score: 5
Accepted
time: 296ms
memory: 33232kb

Extra Test:

score: 0
Extra Test Passed