Submission #673268

#	Time	Username	Problem	Language	Result	Execution time	Memory
673268		smartmonky	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1476 ms	109024 KiB

treearray

#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long

using namespace std;

void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
const int N = 2e5 + 1;
vector <int> g[N];
int up[N][24];
int tin[N], tout[N], timer;
set <int> st[N], st2[N];
void dfs (int v, int p = 0) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i=1; i<=20; ++i)
		up[v][i] = up[up[v][i-1]][i-1];
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (to != p)
			dfs (to, v);
	}
	tout[v] = ++timer;
}

bool upper (int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca (int a, int b) {
	if (upper (a, b))  return a;
	if (upper (b, a))  return b;
	for (int i=20; i>=0; --i)
		if (! upper (up[a][i], b))
			a = up[a][i];
	return up[a][0];
}
main(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0 ; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		g[b].pb(a);
		g[a].pb(b);
	}
	dfs(1, 1);
	vector <int> v(m + 1);
	for(int i = 1 ; i <= m; i++){
		cin >> v[i];
	}
	for(int i = 2; i <= m; i++){
		st[lca(v[i], v[i - 1])].insert(i - 1);
		st2[v[i]].insert(i);
	}
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, val;
			cin >> pos >> val;
			for(int i = pos ; i >= max(pos - 1, 1LL); i--){
				st[lca(v[i], v[i + 1])].erase(i);
			}
			st2[v[pos]].erase(pos);
			v[pos] = val;
			for(int i = pos ; i >= max(pos - 1, 1LL); i--){
				st[lca(v[i], v[i + 1])].insert(i);
			}
			st2[v[pos]].insert(pos);
		}else{
			//cout <<"==";
			int l, r, val;
			cin >> l >> r >> val;
			auto it = st2[val].lower_bound(l);
			if(*it <= r && it != st2[val].end()){
				cout << *it <<" " << *it << endl;
				continue;
			}
			it = st[val].lower_bound(l);
			if(*it < r && it != st[val].end()){
				cout << *it <<" " << *it + 1<< endl;
				continue;
			}
			cout <<"-1 -1" << endl;
		}
	}
}

Compilation message (stderr)

treearray.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~
treearray.cpp: In function 'void fp(std::string)':
treearray.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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