Submission #376030

#	Time	Username	Problem	Language	Result	Execution time	Memory
376030		ijxjdjd	Birthday gift (IZhO18_treearray)	C++14	0 / 100	11 ms	14444 KiB

treearray

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = (int)(2e5) + 5;
const int MAXK = 20;
int a[MAXN];
vector<int> adj[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
int up[MAXN][MAXK];
set<pair<int, int>> sts[MAXN];
void root(int n, int p) {
    up[n][0] = p;
    tin[n] = timer++;
    for (int i = 1; i < MAXK; i++) {
        up[n][i] = up[up[n][i-1]][i-1];
    }
    for (int e : adj[n]) {
        if (e != p) {
            root(e, n);
        }
    }
    tout[n] = timer++;
}
bool is_ancestor(int u, int v) {
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int x, int y) {
    if (is_ancestor(x, y)) {
        return x;
    }
    if (is_ancestor(y, x)) {
        return y;
    }
    for (int i = MAXK-1; i >= 0; i--) {
        if (!is_ancestor(up[x][i], y)) {
            x = up[x][i];
        }
    }
    return up[x][0];
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	FR(i, N-1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
	}
	root(1, 1);
	for (int i = 1; i <= M; i++) cin >> a[i];
	for (int pos = 1; pos <= M; pos++) {
        if (pos > 1) {
            int lc = lca(a[pos], a[pos-1]);
            sts[lc].insert({pos-1, pos});
        }
        sts[a[pos]].insert({pos, -1});
	}
    FR(iter, Q) {
        int id;
        cin >> id;
        if (id == 1) {
            int pos, v;
            cin >> pos >> v;
            if (pos > 1) {
                int lc = lca(a[pos], a[pos-1]);
                sts[lc].erase({pos-1, pos});
                lc = lca(a[pos-1], v);
                sts[lc].insert({pos-1, pos});
            }
            if (pos < M) {
                int lc = lca(a[pos], a[pos+1]);
                sts[lc].erase({pos, pos+1});
                lc = lca(a[pos-1], v);
                sts[lc].insert({pos, pos+1});
            }
            sts[a[pos]].erase({pos, -1});
            sts[v].insert({pos, -1});
            a[pos] = v;
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = (sts[v].lower_bound({l, -1}));
            if (it != sts[v].end() && ((*it) <= make_pair(r, -1))) {
                if ((*it).second == -1) {
                    cout << (*it).first << " " << (*it).first << '\n';
                }
                else {
                    cout << (*it).first << " " << (*it).second << '\n';
                }
            }
            else {
                cout << "-1 -1" << '\n';

            }
        }
    }
	return 0;
}

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