QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490024#9155. 集合strcmp#100 ✓228ms30596kbC++141.4kb2024-07-25 10:27:302024-07-25 10:27:30

Judging History

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

  • [2024-07-25 10:27:30]
  • 评测
  • 测评结果:100
  • 用时:228ms
  • 内存:30596kb
  • [2024-07-25 10:27:30]
  • 提交

answer

#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
#define gc getchar
#define pc putchar
#define rep(i, a, b) for(int i = a; i <= b; i++)
using namespace std;
using ld = double;
typedef unsigned long long int ll;
using pli = pair<ll, int>;
using ppi = pair<pli, int>;
using vec = vector<int>;
const ll inf = 1LL << 60;
constexpr int maxn = 6e5 + 10;
mt19937_64 rd(114514); int n, m, q, T = 5; 
int a[2][maxn][4], R[maxn]; ll w[maxn], h[2][maxn], s[2], B;
inline ll trs(ll k) { return (k << 3 ^ k >> 7 ^ k << 17 ^ k ^ 0x3f5d2a) ^ B; }
inline void add(int p, int del) {
    rep(o, 0, 1) {
        rep(i, 1, 3) {
            int u = a[o][p][i];
            s[o] += trs(h[o][u]), h[o][u] += w[p] * del, s[o] -= trs(h[o][u]);
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &q); rep(i, 1, n) R[i] = n; rd.seed(time(NULL)); B = rd();
    rep(o, 0, 1) rep(i, 1, n) rep(j, 1, 3) scanf("%d", &a[o][i][j]);
    while (T--) {
        rd.seed(rd()); s[0] = s[1] = 0;
        rep(i, 1, n) w[i] = rd(); add(1, 1);
        for (int l = 1, r = 1; l <= n; add(l++, -1)) {
            while (r <= n && s[0] == s[1]) {
                if (++r <= n) add(r, 1);
                else break;
            }
            R[l] = min(R[l], r - 1);
        }
    }
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        puts(r <= R[l] ? "Yes" : "No");
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 110ms
memory: 18220kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 98ms
memory: 12084kb

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 11ms
memory: 12084kb

Pretest #18:

score: 5
Accepted
time: 12ms
memory: 12996kb

Pretest #19:

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

Pretest #20:

score: 5
Accepted
time: 228ms
memory: 28636kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 92ms
memory: 11944kb

Test #16:

score: 5
Accepted
time: 89ms
memory: 12168kb

Test #17:

score: 5
Accepted
time: 5ms
memory: 12008kb

Test #18:

score: 5
Accepted
time: 12ms
memory: 12928kb

Test #19:

score: 5
Accepted
time: 205ms
memory: 18236kb

Test #20:

score: 5
Accepted
time: 220ms
memory: 30596kb

Extra Test:

score: 0
Extra Test Passed