QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471156 | #8338. Quad Kingdoms Chess | chengning0909 | RE | 0ms | 0kb | C++14 | 2.7kb | 2024-07-10 18:44:32 | 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