Submission #861233

#	Time	Username	Problem	Language	Result	Execution time	Memory
861233		Trisanu_Das	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1122 ms	102228 KiB

treearray

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pii pair < int, int >
 
const int maxn = (int) 1e5 + 10;
using namespace std;
int par[20][200200], lift[200200];
vector<int> adj[200200];
int n, m, q;
 
void dfs(int u, int p){
	par[0][u] = p;
	for(int i = 1; i < 19; i++) par[i][u] = par[i - 1][par[i - 1][u]];
	lift[u] = lift[p] + 1;
	for(auto v : adj[u]) if(v != p) dfs(v, u);
}
 
int a[200200];
set<int> S[200200];
set<int> T[200200];
 
int lca(int u, int v){
	if(lift[u] < lift[v]) swap(u, v);
	for(int i = 18; i > -1; i--) if(lift[u] - (1 << i) >= lift[v]) u = par[i][u];
	if(u == v) return u;
	for(int i = 18; i > -1; i--){
		if(par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}
 
int main(){
	cin >> n >> m >> q;
	for(int i = 1, x, y; i < n; i++){
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for(int i = 1; i < m + 1; i++) cin >> a[i];
	dfs(1, 0);
	for(int i = 1; i < m + 1; i++) S[a[i]].insert(i);
	for(int i = 2; i < m + 1; i++) T[lca(a[i], a[i - 1])].insert(i);
	for(int i = 1; i < n + 1; i++) {
		S[i].insert(INT_MAX);
		T[i].insert(INT_MAX);
	}
	while(q--){
        int op, l, r, v; cin >> op;
		if(op == 1){
			cin >> l >> v;
			S[a[l]].erase(l);
			if(l > 1) T[lca(a[l], a[l - 1])].erase(l);
			if(l < m) T[lca(a[l], a[l + 1])].erase(l + 1);
			a[l] = v;
			S[a[l]].insert(l);
			if(l > 1) T[lca(a[l], a[l-1])].insert(l);
			if(l < m) T[lca(a[l], a[l+1])].insert(l + 1);
		}else{
			cin >> l >> r >> v;
			int d = *S[v].lower_bound(l), e = *T[v].lower_bound(l+1);
			if(d <= r) cout << d << ' ' << d << '\n';
			else if(e <= r) cout << e - 1 << ' ' << e << '\n';
			else cout << "-1 -1\n";
		}
	}
}

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