Submission #1024188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024188		Acanikolic	Birthday gift (IZhO18_treearray)	C++14	100 / 100	619 ms	98316 KiB

treearray

#include <bits/stdc++.h>  

#define int long long 

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 2e5 + 10;
 
const int mod = 1e9 + 7;
 
const int inf = 1e9;

const int LOG = 17;

vector<int>g[N];
int up[N][LOG],in[N],out[N],timer = 0,a[N],m;
set<int>st[N][2];

void dfs(int x,int par) {
	in[x] = ++timer;
	up[x][0] = par;
	for(int j = 1; j < LOG; j++) up[x][j] = up[up[x][j - 1]][j - 1];
	for(auto X : g[x]) {
		if(X != par) {
			dfs(X,x);
		}
	}
	out[x] = timer;
}

bool inn(int u,int v) {
	return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u,int v) {
	if(u == inf) return v;
	if(v == inf) return u;
	if(inn(u,v)) return u;
	if(inn(v,u)) return v;
	for(int j = LOG - 1; j >= 0; j--) {
		if(up[u][j] > 0 && !inn(up[u][j],v)) u = up[u][j];
	}
	return up[u][0];
}

void add(int i,bool o) {
	if(i < 1) return;
	if(!o) {
		st[a[i]][0].insert(i);
		return;
	}
	if(i + 1 <= m) {
		st[lca(a[i],a[i + 1])][1].insert(i);
	}
}

void rem(int i,bool o) {
	if(i < 1) return;
	if(!o) {
		st[a[i]][0].erase(i);
		return;
	}
	if(i + 1 <= m) {
		st[lca(a[i],a[i + 1])][1].erase(i);
	}
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 	int n,q;
 	cin >> n >> m >> q;
 	for(int i = 1; i <= n - 1; 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];
 	for(int i = 1; i <= m; i++) add(i,0);
 	for(int i = 1; i + 1 <= m; i++) add(i,1);
 	while(q--) {
 		int type;
 		cin >> type;
 		if(type == 1) {
 			int i,v;
 			cin >> i >> v;
 			rem(i - 1,0);
 			rem(i - 1,1);
 			rem(i,0);
 			rem(i,1);
 			a[i] = v;
 			add(i - 1,0);
 			add(i - 1,1);
 			add(i,0);
 			add(i,1);
 		}else {
 			int l,r,v;
 			cin >> l >> r >> v;
 			int L = -1,R = -1;
 			auto lb = st[v][0].lower_bound(l);
 			if(lb != st[v][0].end() && *lb <= r) L = *lb,R = *lb;
 			auto rb = st[v][1].lower_bound(l);
 			if(rb != st[v][1].end() && *rb < r) L = *rb,R = *rb + 1;
 			cout << L << " " << R << "\n";
 		}
 	}
    return 0;
}

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