Submission #1150547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150547		aktilek	Birthday gift (IZhO18_treearray)	C++20	100 / 100	546 ms	79544 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2e5 + 7;
const int R = 1e9 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int B = 320;

vector < int > g[N];
int a[N], tin[N], tout[N], timer, up[N][22], d[N];
set < int > all[N], lon[N];

void dfs(int v, int p) {
	if (p == 0) up[v][0] = v;
	else up[v][0] = p;
	tin[v] = timer++;
	
	if (p == 0) {
		d[v] = 0;
	} else {
		d[v] = d[p] + 1;
	}
	
	for (int i = 1; i <= 20; i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	
	for (int to : g[v]) {
		if (to == p) continue;
		dfs(to, v);
	}
	tout[v] = timer++;
}

bool upper(int x, int y) {
	if (tin[x] <= tin[y] && tout[y] <= tout[x]) {
		return true;
	}
	return false;
}

int lca(int x, int y) {
	if (upper(x, y)) return x;
	if (upper(y, x)) return y;
	
	for (int i = 20; i >= 0; i--) {
		if (!upper(up[x][i], y)) {
			x = up[x][i];
		}
	}
	return up[x][0];
}

void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	dfs(1, 0);
	
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		lon[a[i]].insert(i);
	}
	
	for (int i = 1; i < m; i++) {
		all[lca(a[i], a[i + 1])].insert(i);
	}
	
	// for (int i = 1; i <= n; i++) {
		// cout << i << ": ";
		// for (int x : all[i]) {
			// cout << x << ' ';
		// }
		// cout << "\n";
	// }
	
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int pos, v;
			cin >> pos >> v;
			all[lca(a[pos], a[pos + 1])].erase(pos);
			all[lca(a[pos], a[pos - 1])].erase(pos - 1);
			lon[a[pos]].erase(pos);
			a[pos] = v;
			all[lca(v, a[pos + 1])].insert(pos);
			all[lca(v, a[pos - 1])].insert(pos - 1);
			lon[a[pos]].insert(pos);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			auto pos = all[v].lower_bound(l);
			int ind = *pos;
			// cout << ind << '\n';
			if (l <= ind && ind < r && pos != all[v].end()) {
				cout << ind << ' ' << ind + 1 << '\n';
				continue;
			}
			
			auto j = lon[v].lower_bound(l);
			if (l <= *j && *j <= r && j != lon[v].end()) {
				cout << *j << ' ' << *j << '\n';
				continue;
			}
			
			cout << -1 << ' ' << -1 << '\n';
		}
	}
	
	// 1: 2, 3
	// 2:
	// 3: 1,
	// 4:
	// 5:  
	
}

int main() {
  	// freopen("gates.in", "r", stdin);
  	// freopen("gates.out", "w", stdout);
  	Fast
  
  	int tc = 1;
  	// cin >> tc;
  
  	while (tc--) {
    	solve();
  	}
}

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