Submission #525451

#	Time	Username	Problem	Language	Result	Execution time	Memory
525451		s_samchenko	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1592 ms	109252 KiB

treearray

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //bad
//#pragma GCC target("avx,avx2")
#define ll long long
#define ull unsigned ll
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
constexpr ll mod = 1e9+7;
const int N = 3e5+100, B = 430;

vector < vector <int> > g, up;
vector <int> d;

void dfs(int v = 1, int pr = 1, int h = 0){
	d[v] = h;
	up[v][0] = pr;
	for (int j = 1; j <= 19; ++j) up[v][j] = up[up[v][j-1]][j-1];
	for (auto to : g[v]){
		if (to == pr) continue;
		dfs(to, v, h+1);
	}
}

int lca(int u, int v){
	if (d[v] < d[u]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int v1 = up[v][j], u1 = up[u][j];
		if (u1 != v1) u = u1, v = v1;
	}
	return up[v][0];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	g.resize(n+1);
	up.resize(n+1, vector <int> (20));
	d.resize(n+1);

	for (int i = 1; i < n; ++i){
		int a, b; cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs();
	vector <int> a(m+1);
	for (int i = 1; i <= m; ++i) cin >> a[i];
	
	vector <set <int> > one(n+1), s(n+1);
	for (int i = 1; i <= m; ++i){
		one[a[i]].insert(i);
		if (i+1 <= m){
			s[lca(a[i], a[i+1])].insert(i);
		}
	}
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, v; cin >> pos >> v;
			one[a[pos]].erase(pos);
			if (pos + 1 <= m) s[lca(a[pos], a[pos+1])].erase(pos);
			if (pos - 1 >= 0) s[lca(a[pos], a[pos-1])].erase(pos-1);

			a[pos] = v;
			
			one[a[pos]].insert(pos);
			if (pos + 1 <= m) s[lca(a[pos], a[pos+1])].insert(pos);
			if (pos - 1 >= 0) s[lca(a[pos], a[pos-1])].insert(pos-1);
			continue;
		}
		int l, r, v; cin >> l >> r >> v;
		auto it1 = one[v].lower_bound(l);
		if (it1 != one[v].end() && *it1 <= r){
			cout << *it1 << " " << *it1 << '\n';
			continue;
		}
		
		auto it = s[v].lower_bound(l);
		if (it != s[v].end() && *it + 1 <= r){
			cout << *it << " " << *it + 1 << '\n';
			continue;
		}
		cout << "-1 -1\n";
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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