Submission #1100561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100561		vjudge1	Birthday gift (IZhO18_treearray)	C++17	100 / 100	914 ms	133704 KiB

treearray

//UNSTOPPABLE
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <pair <int,int> , int>
#define bruh cout << "NO\n"
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,m,q,tin[N],tout[N],up[21][N],timer,a[N];
vector <int> g[N];
set <int> st[N],st1[N];
void dfs(int v , int p = 0){
	tin[v] = ++	timer;
	up[0][v] = p;
	for(int i = 1 ; i <= 20 ; i++){
		up[i][v] = up[i - 1][up[i - 1][v]];
	}
	for(auto to : g[v]){
		if(to == p) continue;
		dfs(to , v);
	}
	tout[v] = timer;
}
bool upper(int a , int b){
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca(int a , int b){
	if(upper(a , b)) return a;
	if(upper(b , a)) return b;
	for(int i = 20 ; i >= 0 ; i--){
		if(!up[i][a]) continue;
		if(!upper(up[i][a] , b)){
			a = up[i][a];
		}
	}
	return up[0][a];
}
void Goldik(){
	cin >> n >> m >> q;
	for(int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}	
	dfs(1);
	for(int i = 1 ; i <= m ; i++){
		cin >> a[i];
		st1[a[i]].insert(i);
	}
	for(int i = 1 ; i < m ; i++){
		st[lca(a[i] , a[i + 1])].insert(i);
	}
	for(int i = 1 ; i <= q ; i++){
		int tp;
		cin >> tp;
		if(tp == 1){
			int pos , x;
			cin >> pos >> x;
			st1[a[pos]].erase(pos);
			if(pos < m){
				st[lca(a[pos] , a[pos + 1])].erase(pos);
			}
			if(pos > 1){
				st[lca(a[pos - 1] , a[pos])].erase(pos - 1);
			}
			a[pos] = x;
			st1[a[pos]].insert(pos);
			if(pos < m){
				st[lca(a[pos] , a[pos + 1])].insert(pos);
			}
			if(pos > 1){
				st[lca(a[pos - 1] , a[pos])].insert(pos - 1);
			}
		}
		else{
			int l,r,v;
			cin >> l >> r >> v;
			if(st1[v].size()){
				auto it = st1[v].lower_bound(l);
				if(it != st1[v].end() && (*it) >= l && (*it) <= r){
					cout << (*it) << ' ' << (*it) << '\n';
					continue;
				}
			}
			if(st[v].size()){
				auto it = st[v].lower_bound(l);
				if(it != st[v].end() && (*it) >= l && (*it) < r){
					cout << (*it) << ' ' << (*it) + 1 << '\n';
					continue;
				}
			}
			cout << "-1 -1\n"; 
		}
	}
}
//rewai mnogo zadach vozmozhno odna iz nih gde to popadetsya
//returning winter prime?
//chem prowe tem luchshe
signed main(/*AZ AZDAN UZDIKSIZ*/){
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Goldik();
	}
}

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