Submission #334911

#	Time	Username	Problem	Language	Result	Execution time	Memory
334911		tengiz05	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1222 ms	80776 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int n, m, k;
vector<int> edges[N];
int tin[N], tout[N];
int up[N][20];
int timer;
void dfs(int u, int p, int d=0){
	tin[u] = timer++;
	up[u][0] = p;
	for(int i=1;i<19;i++)up[u][i] = up[up[u][i-1]][i-1];
	for(auto v : edges[u]){
		if(v != p){
			dfs(v, u,d+1);
		}
	}tout[u] = timer++;
}
bool isancestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
	if(isancestor(u,v))return u;
	if(isancestor(v,u))return v;
	for(int i=18;i>=0;i--){
		if(!isancestor(up[u][i], v))u = up[u][i];
	}return up[u][0];
}
int a[N]; 
set<int> lc[N];
set<int> ar[N];
void solve(int test_case){
	int i, j, q;
	cin >> n >> m >> q;
	for(i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}dfs(1,1);
	for(i=1;i<=m;i++){
		cin >> a[i];
		ar[a[i]].insert(i);
	}
	for(i=1;i<m;i++){
		lc[lca(a[i], a[i+1])].insert(i);
	}
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			ar[a[pos]].erase(pos);
			ar[val].insert(pos);
			if(pos > 1)lc[lca(a[pos], a[pos-1])].erase(pos-1);
			if(pos < m)lc[lca(a[pos], a[pos+1])].erase(pos);
			a[pos] = val;
			if(pos > 1)lc[lca(a[pos], a[pos-1])].insert(pos-1);
			if(pos < m)lc[lca(a[pos], a[pos+1])].insert(pos);
		}else {
			int l, r, v;
			cin >> l >> r >> v;
			auto x = ar[v].lower_bound(l);
			int ansl=-1, ansr=-1;
			if(x != ar[v].end() && *x <= r){
				ansl = ansr = *x;
			}
			auto y = lc[v].lower_bound(l);
			if(y != lc[v].end() && *y < r){
				ansl = (*y);
				ansr = (*y)+1;
			}
			cout << ansl << ' ' << ansr << '\n';
		}
	}
	return;
}
 
signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}
 
 
 
 

Compilation message (stderr)

treearray.cpp: In function 'void solve(int)':
treearray.cpp:43:9: warning: unused variable 'j' [-Wunused-variable]
   43 |  int i, j, q;
      |         ^

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