Submission #1186899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186899		peteza	Birthday gift (IZhO18_treearray)	C++20	100 / 100	662 ms	70168 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

int n, m, q, a, b, c;
set<pair<int, int>> ans[200005];
vector<int> adj[200005];
int arr[200005];
int dep[200005], par[200005][20];

void dfs(int x, int p) {
	par[x][0] = p;
	for(int k=1;k<20;k++) par[x][k] = par[par[x][k-1]][k-1];
	for(auto &e:adj[x]) {
		if(e == p) continue;
		dep[e] = dep[x] + 1;
		dfs(e, x);
	}
}

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	for(int i=19;i>=0;i--) {
		if(dep[a] <= dep[par[b][i]]) b = par[b][i];
	}
	if(a == b) return a;
	for(int i=19;i>=0;i--) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=1;i<n;i++) {
		cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dep[1] = 1; dfs(1, 0);
	for(int i=1;i<=m;i++) cin >> arr[i];
	for(int i=1;i<=m;i++) {
		ans[arr[i]].emplace(i, i);
		if(i != m) ans[lca(arr[i], arr[i+1])].emplace(i, i+1);
	}
	while(q--) {
		cin >> a;
		if(a == 2) {
			cin >> a >> b >> c;
			auto it = ans[c].lower_bound(make_pair(a, a));
			bool heckyeah = 0;
			while(it != ans[c].end()) {
			  if(it->first > b) break;
				if(it->second <= b) {
					cout << it->first << ' ' << it->second << '\n';
					heckyeah = 1;
					break;
				}
				it++;
			}
			if(!heckyeah) cout << "-1 -1\n";
		} else {
			cin >> b >> c;
			ans[arr[b]].erase(make_pair(b, b));
			if(b != 1) ans[lca(arr[b-1], arr[b])].erase(make_pair(b-1, b));
			if(b != m) ans[lca(arr[b], arr[b+1])].erase(make_pair(b, b+1));
			arr[b] = c;
			ans[arr[b]].emplace(b, b);
			if(b != 1) ans[lca(arr[b-1], arr[b])].emplace(b-1, b);
			if(b != m) ans[lca(arr[b], arr[b+1])].emplace(b, b+1);
		}
	}
}

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