QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473128#8338. Quad Kingdoms Chesschengning0909WA 1ms8016kbC++143.0kb2024-07-11 22:09:282024-07-11 22:09:28

Judging History

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

  • [2024-07-11 22:09:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8016kb
  • [2024-07-11 22:09:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

mt19937 rnd;

const int N = 1e5 + 10, mod = 1e9 + 7;

struct Node {
    ll h, past;
    int mmax;
} tr[2][4 * N];

int n, a[N], m, b[N], q;
ll to[N];

void Back(int i, int k) {
    tr[k][i].h = (tr[k][i].h - tr[k][i].past + mod) % mod;
    tr[k][i].past = 0;
}

void update(int i, int l, int r, ll k, int p) {
    tr[p][i].h = (tr[p][i].h + k) % mod;
    tr[p][i].past = (tr[p][i].past + k) % mod;
}

void pushdown(int i, int l, int mid, int r, int p) {
    update(i * 2, l, mid, tr[p][i].h, p);
    update(i * 2 + 1, mid + 1, r, tr[p][i].h, p);
    tr[p][i].h = 0;
}

Node getans(int i, int l, int r, int x, int k) {
    if (l == r) return tr[k][i];
    int mid = (l + r) >> 1;
    pushdown(i, l, mid, r, k);
    return tr[k][i * 2 + 1].mmax >= x ? getans(i * 2 + 1, mid + 1, r, x, k) : getans(i * 2, l, mid, x, k);
}

void Modify(int i, int l, int r, int p, int x, int k) {
    if (l == r) {
        tr[k][i] = {to[x], 0, x};
        return ;
    }
    int mid = (l + r) >> 1;
    pushdown(i, l, mid, r, k);
    p <= mid ? Modify(i * 2, l, mid, p, x, k) : Modify(i * 2 + 1, mid + 1, r, p, x, k);
    tr[k][i].mmax = max(tr[k][i * 2].mmax, tr[k][i * 2 + 1].mmax);
}

void modify(int i, int l, int r, int p, int k) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    pushdown(i, l, mid, r, k);
    Back(i * 2 + 1, k);
    p <= mid ? modify(i * 2, l, mid, p, k) : modify(i * 2 + 1, mid + 1, r, p, k);

    int mmax = tr[k][i * 2 + 1].mmax;
    Node tmp = getans(i * 2, l, mid, mmax, k);
    if (tmp.mmax >= mmax) update(i * 2 + 1, mid + 1, r, tmp.h, k);
}

Node build(int i, int l, int r, int k) {
    if (l == r) return tr[k][i] = (!k ? Node{to[a[l]], 0, a[l]} : Node{to[b[l]], 0, b[l]});
    int mid = (l + r) >> 1;
    build(i * 2, l, mid, k), build(i * 2 + 1, mid + 1, r, k);

    int mmax = tr[k][i * 2 + 1].mmax;
    Node tmp = getans(i * 2, l, mid, mmax, k);
    if (tmp.mmax >= mmax) update(i * 2 + 1, mid + 1, r, tmp.h, k);

    tr[k][i].mmax = max(tr[k][i * 2].mmax, tr[k][i * 2 + 1].mmax);
    return tr[k][i];
}

ll query(int i, int l, int r, int pos, int k) {
    if (l == r) return tr[k][i].h;
    int mid = (l + r) >> 1;
    pushdown(i, l, mid, r, k);
    return pos <= mid ? query(i * 2, l, mid, pos, k) : query(i * 2 + 1, mid + 1, r, pos, k);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    rnd = mt19937(time(0));
    for (int i = 1; i <= 1e5; i++) to[i] = rnd() % mod;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];
    build(1, 1, n, 0), build(1, 1, m, 1);
    cin >> q;
    while (q--) {
        int op, pos, v; cin >> op >> pos >> v;
        if (op == 1) Modify(1, 1, n, pos, v, 0), modify(1, 1, n, pos, 0);
        else Modify(1, 1, m, pos, v, 1), modify(1, 1, m, pos, 1);
        cout << (query(1, 1, n, n, 0) == query(1, 1, m, m, 1) ? "YES\n" : "NO\n");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8016kb

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
NO
NO
NO
NO
YES

result:

wrong answer 4th words differ - expected: 'YES', found: 'NO'