Submission #92482

#	Time	Username	Problem	Language	Result	Execution time	Memory
92482		Nodir_Bobiev	Birthday gift (IZhO18_treearray)	C++14	0 / 100	14 ms	14456 KiB

treearray

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

using namespace std;

const int N = 2e5 + 100;

int n, m, q;
int p[N];
int g[N] = {-1};
int a[N];
vector < int > gr[N];
set < int > st[N];

void dfs(int v, int f)
{
	g[v] = g[f] + 1;
	p[v] = f;
	for(auto to: gr[v])
		if(to != f)
			dfs(to, v);
}

int lca(int v, int u)
{
	if(g[v] > g[u]) return lca(p[v], u);
	if(g[v] < g[u]) return lca(v, p[u]);
	if(v != u) return lca(p[v], u);
	return v;
}

int main()
{
	
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		gr[v].push_back(u);
		gr[u].push_back(v);
	}
	
	for (int i = 1; i <= m; i++)
		cin >> a[i];
	
	dfs(1, 0);
	
	for(int i = 1; i < m;  i++)
		st[lca(a[i], a[i + 1])].insert(i);

	for(int i = 1; i <= m;  i++)
		st[a[i]].insert(i);
	
	set < int > :: iterator lw;
		
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, v;
			cin >> pos >> v;
			if(pos < m)
				st[lca(a[pos], a[pos + 1])].erase(pos);
			if(pos > 1)
				st[lca(a[pos], a[pos - 1])].erase(pos - 1);
			st[a[pos]].erase(pos);
			a[pos] = v;
			st[a[pos]].insert(pos);
			st[lca(a[pos], a[pos + 1])].insert(pos);
			st[lca(a[pos], a[pos - 1])].insert(pos - 1);			
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			lw = st[v].lower_bound(l);
			
			if(lw == st[v].end() || *lw > r)
				cout << -1 << ' ' << -1 << endl;
			
			else if(a[*lw] == v)
				cout << *lw << ' ' << *lw << endl;
			
			else
				cout << *lw << ' ' << *lw + 1 << endl; 
		}
	}
}

/*
 
5 4 4 
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1



*/

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