QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750594#8338. Quad Kingdoms ChessVegetable_DogWA 31ms16164kbC++232.0kb2024-11-15 15:07:172024-11-15 15:07:17

Judging History

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

  • [2024-11-15 15:07:17]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:16164kb
  • [2024-11-15 15:07:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define Rep(i, a, b) for (int i = a; i >= (b); i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define SZ(x) (int)(x.size())
#define lowbit(x) ((x) & -(x))
using db = double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using i128 = __int128_t;
// Think twice, code once

mt19937_64 mrand(time(nullptr));
const int N = 1e5 + 5;
ll val[N];
struct SegmentTree {
    ll h[N << 2];
    int mn[N << 2], mx[N << 2];
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    ll geth(int rt, int x) {
        if (mx[rt] < x) return 0;
        if (mn[rt] >= x) return h[rt];
        if (mx[rs] >= x) return geth(rs, x);
        return geth(ls, x);
    }
    void push_up(int rt) {
        mn[rt] = min(mn[ls], mn[rs]);
        mx[rt] = max(mx[ls], mx[rs]);
        ll hl = geth(ls, mx[rs]);
        h[rt] = hl ^ h[rs];
    }
    void modify(int rt, int l, int r, int x, int d) {
        if (l == r) {
            mn[rt] = mx[rt] = d;
            h[rt] = val[d]; return;
        }
        int md = (l + r) >> 1;
        if (x <= md) modify(ls, l, md, x, d);
        else modify(rs, md + 1, r, x, d);
        push_up(rt);
    }
} tr[2];
void solve() {
    rep(o, 0, 2) {
        int n; cin >> n;
        rep(i, 1, n + 1) {
            int a; cin >> a;
            tr[o].modify(1, 1, N, i, a);
        }
    }
    int q; cin >> q;
    while (q--) {
        int o, x, y; cin >> o >> x >> y; o--;
        tr[o].modify(1, 1, N, x, y);
        if (tr[0].h[1] == tr[1].h[1]) cout << "YES\n";
        else cout << "NO\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    rep(i, 1, N) val[i] = mrand();
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 16164kb

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: -100
Wrong Answer
time: 31ms
memory: 14792kb

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

result:

wrong answer 53rd words differ - expected: 'NO', found: 'YES'