Submission #914222

#	Time	Username	Problem	Language	Result	Execution time	Memory
914222		AlphaMale06	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2420 ms	85548 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

const int N = 2e5+3;
vector<int> adj[N];
int p[18][N];
int tin[N], tout[N];
int timer=-1;
set<pair<int, int>> st;
set<pair<int, int>> st2;

void dfs(int v, int par){
	tin[v]=++timer;
	p[0][v]=par;
	for(int i=1; i<18; i++){
		p[i][v]=p[i-1][p[i-1][v]];
	}
	for(int to : adj[v]){
		if(to!=par)dfs(to, v);
	}
	tout[v]=timer;
}

bool isanc(int u, int v){
	return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca(int u, int v){
	if(isanc(u, v))return u;
	if(isanc(v, u))return v;
	int ret=u;
	for(int i=17; i>=0; i--){
		if(!isanc(p[i][ret], v)){
			ret=p[i][ret];
		}
	}
	return p[0][ret];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0; i< n-1; i++){
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	dfs(1, 0);	
	tin[0]=0; tout[0]=1e9;
	int a[m];
	for(int i=0; i< m; i++){
		cin >> a[i];
		st.insert({a[i], i});
	}
	for(int i=0; i< m-1; i++){
		st2.insert({lca(a[i], a[i+1]), i});
	}
	while(q--){
		int t;
		cin >> t;
		if(t==1){
			int pos, v;
			cin >> pos >> v;
			pos--;
			st.erase({a[pos], pos});
			if(pos!=0){
				st2.erase({lca(a[pos-1], a[pos]), pos-1});
			}
			if(pos!=m-1){
				st2.erase({lca(a[pos], a[pos+1]), pos});
			}
			a[pos]=v;
			st.insert({a[pos], pos});
			if(pos!=0){
				st2.insert({lca(a[pos-1], a[pos]), pos-1});
			}
			if(pos!=m-1){
				st2.insert({lca(a[pos], a[pos+1]), pos});
			}
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			l--; r--;
			auto ptr=st.lower_bound({v, l});
			if(ptr!=st.end()){
				pair<int, int> ans = *ptr;
				if(ans.F==v && ans.S<=r){
					cout << ans.S+1 << " " << ans.S+1 << '\n';
					continue;
				}	
			}
			ptr=st2.lower_bound({v, l});
			if(ptr!=st2.end()){
				pair<int, int> ans = *ptr;
				if(ans.F==v && ans.S<r){
					cout << ans.S+1 << " " << ans.S+2 << '\n';
					continue;
				}
			}
			cout << "-1 -1\n";
		}
	}
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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