Submission #338508

#	Time	Username	Problem	Language	Result	Execution time	Memory
338508		arujbansal	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1511 ms	78692 KiB

treearray

    #include <bits/stdc++.h>
     
    #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
    using namespace std;
    using ll = long long;
     
    const int MAXN = 2e5 + 5, K = 20;
    int n, m, q, timer;
    int a[MAXN], tin[2 * MAXN], tout[2 * MAXN], par[MAXN][K];
    vector<int> g[MAXN];
     
    void dfs(int u, int p) {
        tin[u] = timer++;
     
        for (int j = 1; j < K; j++)
            par[u][j] = par[par[u][j - 1]][j - 1];
     
        for (const auto &v : g[u]) {
            if (v == p) continue;
     
            par[v][0] = u;
            dfs(v, u);
        }
     
        tout[u] = timer - 1;
    }
     
    bool isAnc(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
     
    int query(int u, int v) {
        if (isAnc(u, v)) return u;
        if (isAnc(v, u)) return v;
     
        for (int j = K - 1; j >= 0; j--)
            if (!isAnc(par[u][j], v))
                u = par[u][j];
     
        return par[u][0];
    }
     
    void solve() {
        cin >> n >> m >> q;
     
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
     
            g[u].push_back(v);
            g[v].push_back(u);
        }
     
        timer = 0;
        dfs(0, -1);
     
        set<pair<int, int>> individual;
        vector<set<int>> lca(n + 1);    
     
        for (int i = 0; i < m; i++) {
            cin >> a[i];
            a[i]--;
     
            individual.emplace(a[i], i);
        }
     
        for (int i = 0; i < m - 1; i++) {
            lca[query(a[i], a[i + 1])].insert(i);
        }
     
        while (q--) {
            int type;
            cin >> type;
     
            if (type == 1) {
                int pos, val;
                cin >> pos >> val;
                pos--, val--;
     
                individual.erase(make_pair(a[pos], pos));
                if (pos > 0) lca[query(a[pos], a[pos - 1])].erase(pos - 1);
                if (pos < m - 1) lca[query(a[pos], a[pos + 1])].erase(pos);
     
                a[pos] = val;
     
                individual.emplace(a[pos], pos);
                if (pos > 0) lca[query(a[pos], a[pos - 1])].insert(pos - 1);
                if (pos < m - 1) lca[query(a[pos], a[pos + 1])].insert(pos);
            } else {
                int l, r, val;
                cin >> l >> r >> val;
                l--, r--, val--;
     
                auto single = individual.lower_bound(make_pair(val, l));
                if (single != individual.end()) {
                    int idx = (*single).second;
     
                    if ((*single).first == val && l <= idx && idx <= r) {
                        cout << idx + 1 << " " << idx + 1 << "\n";
                        continue;
                    }
                }
     
                auto adjacent = lca[val].lower_bound(l);
                if (adjacent == lca[val].end() || *adjacent >= r) {
                    cout << "-1 -1\n";
                    continue;
                }
     
                cout << *adjacent + 1 << " " << *adjacent + 2 << "\n";
            }
        }
    }
     
    signed main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
        int tc = 1;
        // cin >> tc;
        while (tc--) solve();
    }

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44