QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471156#8338. Quad Kingdoms Chesschengning0909RE 0ms0kbC++142.7kb2024-07-10 18:44:322024-07-10 18:44:32

Judging History

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

  • [2024-07-10 18:44:32]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-10 18:44:32]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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

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

void update(int i, int l, int r, int len, ll k, int p) {
    if (l == r) {
        tr[p][i].h = (k * P[tr[p][i].len] % mod + tr[p][i].h) % mod;
        tr[p][i].len += len;
    } else {
        tr[p][i].lazy = (k * P[tr[p][i].lylen] % mod + tr[p][i].lazy) % mod;
        tr[p][i].lylen += len;
    }
}

void pushdown(int i, int l, int mid, int r, int p) {
    update(i * 2, l, mid, tr[p][i].lylen, tr[p][i].lazy, p);
    update(i * 2 + 1, mid, r, tr[p][i].lylen, tr[p][i].lazy, p);
    tr[p][i].lazy = tr[p][i].lylen = 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] = {x, 0, x, 0, 1};
        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);

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

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

Node build(int i, int l, int r, int k) {
    if (l == r) return tr[k][i] = (!k ? Node{a[l], 0, a[l], 0, 1} : Node{b[l], 0, b[l], 0, 1});
    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);
    update(i * 2 + 1, mid + 1, r, tmp.len, tmp.h, k);

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

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);
    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);
        else modify(1, 1, m, pos, v, 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
Runtime Error

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:


result: