Submission #667301

#	Time	Username	Problem	Language	Result	Execution time	Memory
667301		Kaztaev_Alisher	Birthday gift (IZhO18_treearray)	C++17	0 / 100	8 ms	14420 KiB

treearray

//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long  , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x  << " = " << x << endl;
#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;

const ll N = 2e5+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;

using namespace std;

int n , m , q , a[N];
int dep[N] , up[N][20] ;
vector<int> g[N];
set<int> st1[N];
set<pii> st;
void dfs(int v, int p){
	dep[v] = dep[p]+1;
 	up[v][0] = p;
	for(int i = 1; i < 20; i++){
		up[v][i] = up[up[v][i-1]][i-1]; 
	}
	for(int to : g[v]){
		if(to == p) continue;
		dfs(to , v);
	}
}
int lca(int a , int b){
	if(dep[a] > dep[b]) swap(a , b);
	for(int i = 19; i >= 0; i--){
		if(dep[up[b][i]] >= dep[a]){
			b = up[b][i];
		}
	}
	if(b == a) return a;
	for(int i = 19; i >= 0; i--){
		if(up[b][i] != up[a][i]){
			b = up[b][i];
			a = up[a][i];
		}
	}
	return up[b][0];
}

void solve(){
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}	
	dfs(1 , 0);
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		if(i) st.ins({lca(a[i] , a[i-1]) , i-1});
		st1[a[i]].ins(i);
	}
	while(q--){
		int tp;
		cin >> tp;
		if(tp == 1){
			int pos , v; 
			cin >> pos >> v;
			st1[a[pos]].ers(pos);
			if(pos-1 >= 1) st.ers({lca(a[pos] , a[pos-1]) , pos-1});
			if(pos+1 <= m) st.ers({lca(a[pos] , a[pos+1]) , pos});
			a[pos] = v;
			st1[a[pos]].ins(pos);
			if(pos-1 >= 1) st.ers({lca(a[pos] , a[pos-1]) , pos-1});
			if(pos+1 <= m) st.ers({lca(a[pos] , a[pos+1]) , pos});
		} else {
			int l , r , v;
			cin >> l >> r >> v;
			auto it = st1[v].lower_bound(l);
			if(it != st1[v].end()){
				if(*it <= r){
					cout << *it <<" " << *it << "\n";
					continue;
				}
			}
			auto it1 = st.lower_bound({v , l});
			if(it1 != st.end()){
				pii a = *it1; 
				if(a.F == v && a.S <= r-1){
					cout << a.S <<" " << a.S+1 << "\n";
					continue;
				}
			}
			cout << -1 << " " << -1 <<"\n";
		}
	}
}
signed main(){
	ios;
	solve();
	return 0;
}
/*
11 
1 2
2 3
2 4
1 5
5 6
6 7
6 8
5 9 
9 10
9 11
*/
 	

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