QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409897#8338. Quad Kingdoms ChessbigJTL 48ms4260kbC++204.4kb2024-05-12 21:22:262024-05-12 21:22:27

Judging History

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

  • [2024-05-12 21:22:27]
  • 评测
  • 测评结果:TL
  • 用时:48ms
  • 内存:4260kb
  • [2024-05-12 21:22:26]
  • 提交

answer

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

constexpr bool isprime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

constexpr int findPrime(int n) {
    while (!isprime(n)) {
        n++;
    }
    return n;
}

std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
const int P = 998244353;
const int B = rnd() % P;

constexpr int N = 100000;
int p[N + 1];

template <class Info>
struct SegmentTree {
#define m (l + r) / 2
    int n;
    std::vector<Info> tr;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        tr.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                tr[p] = init_[l];
                tr[p].l = l;
                tr[p].r = r;
                return;
            }
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }

    void pull(int p) {
        tr[p] = merge(tr[2 * p], tr[2 * p + 1], *this);
    }

    void modify(int p, int l, int r, int x, const Info& v) {
        if (r - l == 1) {
            tr[p] = v;
            tr[p].l = l;
            tr[p].r = r;
            return;
        }
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int x, const Info& v) {
        modify(1, 0, n, x, v);
    }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return tr[p];
        }
        return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y), *this);
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }

    int find(int p, int l, int r, int x, int y, int v) {
        if (l >= y || r <= x || tr[p].max < v) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int res = find(2 * p, l, m, x, y, v);
        if (res == -1) {
            res = find(2 * p + 1, m, r, x, y, v);
        }
        return res;
    }
    int find(int x, int y, int v) {
        return find(1, 0, n, x, y, v);
    }

#undef m
};

struct Info {
    int l;
    int r;
    int max;
    int hash;
    int siz;
    Info(int v = 0) : l(-1), r(-1), max(v), hash(1LL * v * B % P), siz(1) {}
};

Info merge(const Info& a, const Info& b, SegmentTree<Info>& seg) {
    if (a.l == -1) {
        return b;
    } else if (b.l == -1) {
        return a;
    }
    if (a.max > b.max) {
        Info c = a;
        c.r = a.r;
        return c;
    }
    int pos = seg.find(b.l, b.r, a.max);
    if (pos == -1) {
        pos = b.l;
    }
    Info d = seg.rangeQuery(pos, b.r);
    Info c{};
    c.l = a.l;
    c.r = b.r;
    c.max = std::max(a.max, b.max);
    c.siz = a.siz + d.siz;
    c.hash = (a.hash + 1LL * d.hash * p[a.siz] % P) % P;
    return c;
}

int main() {
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = (1LL * p[i - 1] * B) % P;
    }

    int n1, n2, m;

    scanf("%d", &n1);
    std::vector<int> a(n1);
    for (int i = 0; i < n1; i++) {
        scanf("%d", &a[i]);
    }

    scanf("%d", &n2);
    std::vector<int> b(n2);
    for (int i = 0; i < n2; i++) {
        scanf("%d", &b[i]);
    }

    std::ranges::reverse(a);
    std::ranges::reverse(b);

    SegmentTree<Info> sega(a);
    SegmentTree<Info> segb(b);

    for (scanf("%d", &m); m; m--) {
        int o, x, y;
        scanf("%d%d%d", &o, &x, &y);
        if (o == 1) {
            sega.modify(n1 - x, y);
        } else {
            segb.modify(n2 - x, y);
        }
        puts(sega.tr[1].hash == segb.tr[1].hash ? "YES" : "NO");
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4216kb

input:

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

output:

NO
NO
NO
YES
NO
NO
NO
YES

result:

ok 8 tokens

Test #2:

score: 0
Accepted
time: 37ms
memory: 3972kb

input:

1
2
6
2 1 1 1 1 1
200000
2 6 2
1 1 1
1 1 1
1 1 2
2 1 1
1 1 2
1 1 1
2 4 1
2 1 2
1 1 1
1 1 2
2 5 1
1 1 1
1 1 2
1 1 1
2 6 1
1 1 2
1 1 2
1 1 2
2 3 1
1 1 1
2 1 1
2 6 2
1 1 2
2 4 1
1 1 2
2 6 1
1 1 2
1 1 1
2 5 2
2 6 2
1 1 1
2 4 2
2 5 2
2 6 2
1 1 1
2 5 1
2 6 2
1 1 2
1 1 1
1 1 1
2 4 1
1 1 2
1 1 2
1 1 2
2 3 2...

output:

NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #3:

score: 0
Accepted
time: 32ms
memory: 4052kb

input:

6
2 1 1 2 1 2
1
1
200000
2 1 1
1 1 2
1 1 1
2 1 2
2 1 1
2 1 1
2 1 2
2 1 2
1 1 2
1 3 1
1 6 2
1 5 2
1 4 2
1 3 1
2 1 2
1 4 2
1 4 2
2 1 2
2 1 2
1 3 1
1 6 1
1 1 2
2 1 1
1 6 1
1 3 1
1 5 2
1 6 2
1 5 2
2 1 2
1 2 1
1 5 2
2 1 1
2 1 1
1 6 1
2 1 2
2 1 1
1 3 2
2 1 1
1 6 1
1 4 2
1 2 1
1 1 1
2 1 1
1 2 1
1 6 2
1 6 2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #4:

score: 0
Accepted
time: 47ms
memory: 4052kb

input:

6
1 3 1 2 1 2
6
2 1 3 3 3 1
200000
2 4 2
1 2 1
1 6 2
2 3 2
1 1 1
1 6 2
1 6 2
1 3 2
2 6 1
2 4 3
1 1 2
2 5 2
2 6 2
2 3 1
1 4 3
1 3 1
2 5 2
2 4 2
2 1 3
1 1 1
2 2 2
2 4 2
1 5 3
1 6 3
2 6 3
1 5 3
2 5 3
2 4 1
2 4 2
1 1 2
1 6 1
2 6 1
1 2 3
1 1 3
1 1 1
2 6 3
2 4 1
1 4 2
2 2 1
1 3 1
1 1 3
1 1 3
1 4 3
1 3 3
2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #5:

score: 0
Accepted
time: 31ms
memory: 4160kb

input:

4
1 1 2 2
1
1
200000
2 1 2
1 1 3
1 2 1
2 1 2
2 1 2
2 1 3
2 1 1
2 1 1
1 4 2
2 1 3
1 3 1
1 2 1
1 3 2
2 1 1
1 4 2
2 1 1
2 1 2
1 1 1
2 1 2
2 1 1
1 4 1
1 2 2
2 1 1
1 1 1
1 4 3
2 1 3
1 1 3
2 1 2
1 2 1
2 1 1
2 1 1
2 1 1
2 1 3
2 1 2
1 2 3
2 1 3
1 3 3
2 1 1
1 2 3
2 1 2
1 1 2
2 1 2
2 1 3
1 2 1
1 4 3
2 1 2
2 1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #6:

score: 0
Accepted
time: 29ms
memory: 4112kb

input:

2
4 2
4
2 3 3 2
200000
1 1 2
1 2 2
1 2 2
1 2 4
1 1 2
1 2 4
2 2 1
1 1 3
2 3 2
2 3 1
2 2 4
2 3 2
2 2 1
1 1 4
1 2 4
2 2 1
1 1 2
2 1 2
2 4 4
1 2 4
1 2 3
2 4 4
2 3 1
2 1 3
2 3 1
2 2 1
1 1 2
2 2 1
1 2 3
1 2 2
1 2 1
1 2 4
1 2 4
1 1 3
1 1 4
2 1 3
1 1 1
1 2 4
2 1 2
2 3 4
1 2 4
2 2 1
1 2 1
2 3 2
1 2 3
2 3 3
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #7:

score: 0
Accepted
time: 47ms
memory: 4036kb

input:

7
3 3 4 1 1 3 3
5
3 3 2 1 4
200000
2 2 1
2 2 1
2 5 1
1 6 1
1 5 2
2 1 4
1 4 2
1 6 4
1 7 1
1 2 3
2 5 1
2 5 4
1 6 2
1 5 2
1 4 1
1 2 1
2 2 2
1 3 4
1 7 2
1 6 3
2 5 1
1 5 1
1 7 3
2 1 3
2 3 1
1 3 2
2 2 2
1 7 4
2 1 4
1 3 2
1 1 2
1 5 3
1 5 3
2 2 2
1 5 3
2 5 3
2 3 2
1 1 3
1 2 2
2 2 1
2 1 4
2 1 2
1 3 4
2 1 1
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #8:

score: 0
Accepted
time: 37ms
memory: 4052kb

input:

1
3
7
4 4 5 5 5 5 4
200000
2 2 4
2 6 4
1 1 4
2 6 4
2 1 3
2 2 3
2 1 3
1 1 5
1 1 5
2 3 5
1 1 4
1 1 4
2 6 5
2 5 1
2 1 2
2 7 2
1 1 5
2 4 5
1 1 2
1 1 3
2 4 2
2 1 3
1 1 3
2 1 1
1 1 1
2 3 1
1 1 4
1 1 5
1 1 1
2 5 2
2 7 3
1 1 5
2 6 4
1 1 4
2 7 4
2 3 3
2 3 1
1 1 3
1 1 3
2 4 4
1 1 4
1 1 2
1 1 1
2 3 1
2 1 1
1 1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #9:

score: 0
Accepted
time: 42ms
memory: 4004kb

input:

8
3 1 2 2 1 4 4 4
3
1 4 4
200000
1 2 1
1 5 1
2 1 1
2 1 1
2 2 2
2 3 1
1 5 5
1 6 2
1 2 5
1 3 1
1 5 1
2 1 5
2 1 2
1 4 4
2 3 3
1 4 3
2 2 2
2 3 1
1 6 4
1 1 3
1 2 3
2 2 5
2 3 3
2 1 3
2 3 4
2 1 4
2 2 5
2 2 4
2 2 2
1 3 1
1 8 2
2 2 3
1 2 2
1 1 2
1 1 1
1 3 1
2 1 3
2 2 3
1 6 2
2 2 4
1 6 3
2 1 1
1 1 4
2 1 4
2 1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #10:

score: 0
Accepted
time: 32ms
memory: 4156kb

input:

3
6 1 5
2
5 3
200000
1 2 4
1 1 3
1 2 5
2 2 5
1 3 3
1 1 6
1 3 1
1 2 1
2 1 6
2 1 4
2 1 2
2 2 3
1 3 1
1 3 5
1 2 4
2 2 5
1 2 5
1 3 1
2 1 3
1 2 6
1 2 4
2 1 3
1 2 4
1 2 1
1 3 2
2 2 6
2 1 4
2 2 4
1 1 2
1 1 4
2 2 2
2 1 4
1 2 2
1 1 3
2 1 4
1 3 3
2 1 6
2 2 2
1 1 6
1 3 6
1 2 2
1 3 1
2 2 3
1 2 2
2 1 2
2 2 5
2 2...

output:

NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #11:

score: 0
Accepted
time: 35ms
memory: 4260kb

input:

3
1 1 6
5
2 3 4 4 6
200000
2 3 5
2 5 5
1 1 4
1 2 4
1 1 1
2 4 3
2 1 2
1 1 6
2 2 2
2 5 4
1 3 4
1 3 4
2 3 5
2 1 6
1 1 1
2 3 4
2 3 5
2 2 5
1 1 5
1 2 2
1 3 2
2 2 1
1 3 5
2 3 6
1 3 3
2 1 3
2 5 3
1 1 1
2 4 4
2 5 1
2 2 5
1 2 2
1 2 3
2 4 5
1 3 5
2 1 1
2 5 1
1 2 1
2 5 4
2 3 1
2 1 6
1 1 2
1 3 6
1 2 1
2 3 6
1 1...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 200000 tokens

Test #12:

score: 0
Accepted
time: 48ms
memory: 4156kb

input:

8
73198 31688 65092 21397 35031 58089 52944 16010
5
31090 97692 26708 44940 89767
200000
2 5 31191
1 1 60759
1 6 70508
1 2 97983
2 3 53563
1 4 22102
1 7 36211
1 3 33339
1 8 49224
1 7 82146
2 5 97668
1 4 13552
1 2 26414
2 4 3381
1 4 42198
1 4 28786
2 2 29892
2 2 77347
1 5 53766
2 5 55142
2 5 74266
1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #13:

score: -100
Time Limit Exceeded

input:

100000
45952 97807 4941 35929 10776 28013 47912 21386 48030 55110 1347 96260 91732 78252 37717 2556 44017 67045 91588 59689 86623 88384 41158 38652 77627 83554 48557 85544 94827 54704 86949 61451 79790 92480 74798 43911 65450 20096 17129 95952 87522 98877 41827 51143 42419 98384 27210 34607 91233 46...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result: