Submission #1036980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036980		goduadzesaba	Birthday gift (IZhO18_treearray)	C++17	0 / 100	5 ms	29356 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fr first
#define sc second
const int N=2e5+5,mod=1e9+7;
int t,n,m,q,x,y,z,a1,a2,cur,tin[N],tout[N],par[N][20],a[N],b[N];
vector <int> v[N]; set <int> s1[N],s2[N];
void dfs (int g,int p){
	cur++; tin[g]=cur;
	par[g][0]=p;
	for (int i=1; i<20; i++)
		par[g][i]=par[par[g][i-1]][i-1];
	for (int i:v[g]){
		if (i==p) continue;
		dfs(i,g);
	}
	tout[g]=cur;
}
bool ispar(int a,int b){
	if (tin[a]<=tin[b] && tout[a]>=tout[b])
		return 1;
	return 0;
}
int lca(int a,int b){
	if (ispar(a,b)) return a;
	for (int i=19; i>=0; i--)
		if (par[a][i]>0 && !ispar(par[a][i],b))
			a=par[a][i];
	return par[a][0];
}
signed main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for (int i=1; i<n; i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	for (int i=1; i<=m; i++){
		cin>>a[i];
		s1[a[i]].insert(i);
	}
	for (int i=1; i<m; i++){
		b[i]=lca(a[i],a[i+1]);
		s2[b[i]].insert(i);
	}
	while (q--){
		cin>>t;
		if (t==1){
			cin>>x>>y;
			s1[a[x]].erase(x);
			a[x]=y;
			s1[a[x]].insert(x);
			
			s2[b[x]].erase(x);
			b[x]=lca(a[x],a[x+1]);
			s2[b[x]].insert(x);
			
			s2[b[x-1]].erase(x-1);
			b[x-1]=lca(a[x-1],a[x]);
			s2[b[x-1]].insert(x-1);
		}
		else{
			cin>>x>>y>>z;
			a1=a2=n+1;
			if (s1[z].lower_bound(x)!=s1[z].end())
				a1=*s1[z].lower_bound(x);
			if (s2[z].lower_bound(x)!=s2[z].end())
				a2=*s2[z].lower_bound(x);
			if (a1<=y) cout<<a1<<" "<<a1;
			else if (a2<y) cout<<a2<<" "<<a2+1;
			else cout<<"-1 -1";
			cout<<"\n";
		}
	}
}

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