제출 #1162379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162379		ahmedhali107	Klasika (COCI20_klasika)	C++20	110 / 110	3107 ms	186304 KiB

klasika

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;

const char nl = '\n';

struct segTree {
    int N;
    vector<set<int>> sg;

    segTree(int n) {
        N = 1;
        while (N < n) N <<= 1;
        sg.assign(N << 1, {});
    }

    int get_max(const set<int> &st, int x) {
        if (st.empty()) return 0;
        const int B = 30;
        int cur = 0, mx = (1 << B) - 1;
        for (int i = B; ~i; i--) {
            int bit = !(x >> i & 1);
            if (bit) {
                int ncur = cur | (1 << i);
                auto mnit = st.lower_bound(ncur);
                auto mxit = st.upper_bound(mx);
                if (mnit != st.end() && mxit != st.begin() && *mnit <= *prev(mxit)) {
                    cur = ncur;
                } else {
                    mx &= ~(1 << i);
                }
            } else {
                int nmx = mx & ~(1 << i);
                auto mnit = st.lower_bound(cur);
                auto mxit = st.upper_bound(nmx);
                if (mnit != st.end() && mxit != st.begin() && *mnit <= *prev(mxit)) {
                    mx = nmx;
                } else {
                    cur |= 1 << i;
                }
            }
        }
        return x ^ cur;
    }

    void update(int i, int x) {
        for (i += N; i; i >>= 1) {
            sg[i].insert(x);
        }
    }

    int query(int l, int r, int x) {
        int ans = 0;
        for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) ans = max(ans, get_max(sg[l++], x));
            if (r % 2 == 0) ans = max(ans, get_max(sg[r--], x));
        }
        return ans;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(1);
    vector<int> a(1);
    vector<array<int, 3>> qs(n);
    for (int i = 0; i < n; i++) {
        string t;
        cin >> t;
        if (t == "Add") {
            int u, x;
            cin >> u >> x, --u;
            g[u].push_back(g.size());
            a.push_back(a[u] ^ x);
            qs[i] = {1, (int) g.size(), 0};
            g.emplace_back();
        } else {
            int u, v;
            cin >> u >> v, --u, --v;
            qs[i] = {2, u, v};
        }
    }
    int timer = -1;
    vector<int> tin(n), tout(n);
    auto dfs = [&](auto &&dfs, int u) -> void {
        tin[u] = ++timer;
        for (int v: g[u]) dfs(dfs, v);
        tout[u] = timer;
    };
    dfs(dfs, 0);
    segTree sg(n);
    sg.update(0, 0);
    for (auto &[t, u, v]: qs) {
        if (t == 1) {
            sg.update(tin[u], a[u]);
        } else {
            cout << sg.query(tin[v], tout[v], a[u]) << nl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
// #ifndef ONLINE_JUDGE
//     freopen("../in.txt", "r", stdin);
//     freopen("../out.txt", "w", stdout);
// #endif
    solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44