제출 #1283688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283688		Jawad_Akbar_JJ	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1826 ms	71720 KiB

treearray

#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int N = 1<<18;
vector<int> nei[N];
set<pair<int, int>> Vc[N];
int par[N][18], hei[N], ps[N];

void dfs(int u, int p){
	par[u][0] = p, hei[u] = hei[p] + 1;
	for (int i=1;i<18;i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for (int i : nei[u])
		if (i != p)
			dfs(i, u);
}

int Lca(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);
	for (int i=17;i>=0;i--){
		if ((1<<i) + hei[u] <= hei[v])
			v = par[v][i];
	}
	for (int i=17;i>=0;i--){
		if (par[u][i] != par[v][i])
			u = par[u][i], v = par[v][i];
	}
	return (u == v ? u : par[u][0]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, q;
	cin>>n>>m>>q;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	dfs(1, 0);

	for (int i=1;i<=m;i++){
		cin>>ps[i];
		if (i > 1)
			Vc[Lca(ps[i], ps[i-1])].insert({i-1, i});
		Vc[ps[i]].insert({i, i});
	}

	for (int i=1, t, l, r, pos, v;i<=q;i++){
		cin>>t;
		if (t == 1){
			cin>>pos>>v;
			Vc[ps[pos]].erase({pos, pos});

			if (pos > 1){
				Vc[Lca(ps[pos], ps[pos-1])].erase({pos-1, pos});
				Vc[Lca(v, ps[pos-1])].insert({pos-1, pos});
			}
			if (pos < m){
				Vc[Lca(ps[pos], ps[pos+1])].erase({pos, pos+1});
				Vc[Lca(v, ps[pos+1])].insert({pos, pos+1});
			}

			ps[pos] = v;
			Vc[v].insert({pos, pos});
			continue;
		}

		cin>>l>>r>>v;
		auto u = Vc[v].upper_bound({l, l-1});

		if (u != Vc[v].end() and (*u).second <= r)
			cout<<(*u).first<<" "<<(*u).second<<'\n';
		else
			cout<<"-1 -1\n";
	}
}

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