Submission #719438

#	Time	Username	Problem	Language	Result	Execution time	Memory
719438		Doncho_Bonboncho	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1067 ms	189032 KiB

treearray

#include <algorithm>
#include <bits/stdc++.h>
#include <iomanip>
#include <map>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

std::vector<int> v[MAX_N];
int a[MAX_N];
std::set<int> pos[MAX_N];
std::set<int> lcaPos[MAX_N];

int lca[MAX_N][30];
int dep[MAX_N];
bool viz[MAX_N];
void dfs( int x ){
	viz[x] = true;
	for( auto j : v[x] ){
		if( !viz[j] ){
			dep[j] = dep[x] +1;
			lca[j][0] = x;
			dfs(j);
		}
	}
}

int st;
int getLca( int a, int b ){
	if( dep[a] > dep[b] ) std::swap( a, b );
	int diff = dep[b] - dep[a];
	for( int i = st-1 ; i>=0 ; i-- ){
		if( (diff>>i)&1 ) b = lca[b][i];
	}
	if( a == b ) return a;
	for( int i=st-1 ; i>=0 ; i-- ){
		if( lca[a][i] != lca[b][i] ){
			a = lca[a][i];
			b = lca[b][i];
		}
	}
	return lca[a][0];
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n, m, q;
	std::cin>>n>>m>>q;
	for( int i=0 ; i<n-1 ; i++ ){
		int a, b;
		std::cin>>a>>b; a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(0);

	st = 0;
	while( true ){
		st ++;
		if( (1<<st) > n ) break;
		for( int i=0 ; i<n ; i++ ) lca[i][st] = lca[lca[i][st-1]][st-1];
	}

	for( int i=0 ; i<m ; i++ ){
		std::cin>>a[i]; a[i]--;
		pos[a[i]].insert(i);
		if( i ) lcaPos[ getLca(a[i-1], a[i]) ].insert(i-1);
	}

	while( q-- ){
		int t;
		std::cin>>t;
		if( t == 1 ){
			int p, v;
			std::cin>>p>>v; p--; v--;
			pos[a[p]].erase(p);
			pos[v].insert(p);
			if( p ){
				lcaPos[getLca( a[p-1], a[p] )].erase(p-1);
				lcaPos[getLca( a[p-1], v )].insert(p-1);
			}
			if( p < m-1 ){
				lcaPos[getLca( a[p], a[p+1] )].erase(p);
				lcaPos[getLca( v, a[p+1] )].insert(p);
			}
			a[p] = v;
		}else{
			int l, r, v;
			std::cin>>l>>r>>v;
			l--; r--; v--;
			
		//	std::cerr<<" ! "<<v<<"\n";
		//	for( auto j : pos[v] ) std::cerr<<j<<" ";
		//	std::cerr<<"\n\n";

			auto it = pos[v].lower_bound(l);
			if( it != pos[v].end() and *it <= r ){
				std::cout<<*it+1<<" "<<*it+1<<"\n";
				continue;
			}

			it = lcaPos[v].lower_bound(l);
			if( it != lcaPos[v].end() and *it <= r-1 ){
				std::cout<<*it+1<<" "<<*it+2<<"\n";
				continue;
			}
			std::cout<<"-1 -1\n";
		}
	}
	

	return 0;
}

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