oj.uz

Submission #882633

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

const int N = 2e5 + 5,inf = 1e18;

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];

	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);
	}

	for (int i = 1; i <= m; i++){
		st[arr[i]].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) upd(pos-1,0);
			if (pos + 1 <= m) upd(pos,0);
			arr[pos] = val;
			if (pos >= 1) upd(pos-1,1);
			if (pos + 1 <= m) upd(pos,1);
		}else{
			int l,r,x;
			cin>>l>>r>>x;

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 53852 KB n=5
2 Runtime error 48 ms 109128 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 10 ms 53852 KB n=5
2 Runtime error 48 ms 109128 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 10 ms 53852 KB n=5
2 Runtime error 48 ms 109128 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 10 ms 53852 KB n=5
2 Runtime error 48 ms 109128 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -