oj.uz

Submission #882654

# Submission time Handle Problem Language Result Execution time Memory
882654 2023-12-03T12:43:01 Z NintsiChkhaidze Birthday gift (IZhO18_treearray) C++17
0 / 100
 35 ms 79948 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
#define pb push_back
#define pii pair <int,int>
using namespace std;

const int N = 2e5 + 5;
int dp[N],d[25][N],arr[N];
vector <int> v[N];
multiset <int> vec[N],st[N];

void dfs(int x,int par){
	d[0][x] = par;
	dp[x] = dp[par] + 1;
	for (int to: v[x])
		if (to != par) dfs(to,x);
}

int lca(int x,int y){
	if (dp[x] < dp[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dp[d[i][x]] >= dp[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x], y = d[i][y];

	return d[0][x];
}

void upd(int idx,int p){
	int x = arr[idx],y = arr[idx + 1];
	int c = lca(x,y);

	if (!p) vec[c].erase(vec[c].find(idx));
	else vec[c].insert(idx);
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,q;
	cin>>n>>m>>q;

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

	for (int i = 1; i <= m; i++)
		cin >> arr[i],st[arr[i]].insert(i);

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i < m; i++){
		int c = lca(arr[i],arr[i + 1]);
		vec[c].insert(i);
	}

	while (q--){
		int tp;
		cin>>tp;

		if (tp == 1){
			int pos,val;
			cin>>pos>>val;

			st[arr[pos]].erase(st[arr[pos]].find(pos));
			st[val].insert(pos);

			if (pos >= 1 && pos < m) upd(pos-1,0);
			if (pos >= 1 && pos < m) upd(pos,0);

			arr[pos] = val;
			
			if (pos >= 1 && pos < m) upd(pos-1,1);
			if (pos >= 1 && pos < m) upd(pos,1);
		}else{
			int l,r,x;
			cin>>l>>r>>x;

			multiset <int> :: iterator it;
			if (st[x].size()){
				it = st[x].lower_bound(l);
				if (it != st[x].end() && (*it) <= r){
					cout<<(*it)<<" "<<(*it)<<endl;
					continue;
				}
			}

			if (vec[x].size()){
				it = vec[x].lower_bound(l);
				if (it != vec[x].end() && (*it) < r){
					cout<<*it<<" "<<(*it) + 1<<endl;
					continue;
				}
			}
			cout<<-1<<" "<<-1<<endl;
		}
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB n=5
2 Runtime error 35 ms 79948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB n=5
2 Runtime error 35 ms 79948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB n=5
2 Runtime error 35 ms 79948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB n=5
2 Runtime error 35 ms 79948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -