Submission #1270590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270590		vulestamenkovic	Birthday gift (IZhO18_treearray)	C++20	0 / 100	2 ms	1860 KiB

treearray

#include<bits/stdc++.h>
#define MAXN (int)2e5+5
#define int long long
using namespace std;
int n;
vector<int>g[MAXN];
int lg[MAXN],l[MAXN][23],d[MAXN],a[MAXN],b[MAXN];
void dfs(int x,int p){
	for(int i=1;i<=lg[n];i++){
		l[x][i]=(l[x][i-1]==-1?-1:l[l[x][i-1]][i-1]);
	}
	for(int&y:g[x]){
		if(y^p){
			d[y]=d[x]+1;
			l[y][0]=x;
			dfs(y,x);
		}
	}
}int lift(int x,int k){
	int h=x;
	for(int i=0;i<=lg[n];i++){
		if((1ll<<i)&k){
			h=l[h][i];
			if(h==-1){return -1;}
		}
	}
	return h;
}int lca(int x,int y){
	if(d[y]>d[x]){
		swap(x,y);
	}
	x=lift(x,d[x]-d[y]);
	for(int i=lg[n];i>=0;i--){
		if(l[x][i]!=l[y][i]){
			x=l[x][i];
			y=l[y][i];
		}
	}
	return l[x][0];
}
void solve() {
	int m,q;cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	d[1]=0;
	l[1][0]=-1;
	dfs(1,0);
	map<int,set<int>>p,p2;
	for(int i=0;i<m;i++){
		cin>>a[i];
		p[a[i]].insert(i);
	}for(int i=0;i<m-1;i++){
		b[i]=lca(a[i],a[i+1]);
		p2[b[i]].insert(i);
	}while(q--){
		int t;cin>>t;
		if(t==1){
			int i,v;cin>>i>>v;i--;
			p[a[i]].erase(p[a[i]].find(i));
			a[i]=v;
			p[a[i]].insert(i);
			if(i<m-1){
				p2[b[i]].erase(p2[b[i]].find(i));
				b[i]=lca(a[i],a[i+1]);
				p2[b[i]].insert(i);
			}if(i>0){
				p2[b[i-1]].erase(p2[b[i-1]].find(i-1));
				b[i-1]=lca(a[i-1],a[i]);
				p2[b[i-1]].insert(i-1);
			}
		}else{
			int l,r,v;cin>>l>>r>>v;l--;r--;
			auto lb=p[v].lower_bound(l);
			if(lb!=p[v].end()&&*lb<=r){
				cout<<(*lb)+1<<' '<<(*lb)+1<<'\n';continue;
			}
			lb=p2[v].lower_bound(l);
			if(lb!=p2[v].end()&&*lb<r){
				cout<<(*lb)+1<<' '<<(*lb)+2<<'\n';continue;
			}
			cout<<-1<<' '<<-1<<'\n';
		}
	}
}
int32_t main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int32_t T=1;//cin>>T;
	for(int i=2;i<MAXN;i++){
		lg[i]=lg[i/2]+1;
	}
	while(T--) {
		solve();
	}
	return 0;
}

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