Submission #338539

#	Time	Username	Problem	Language	Result	Execution time	Memory
338539		shivensinha4	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1202 ms	141592 KiB

treearray

#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
class SparseTable {
	vector<vector<ii>> st;
	vi log; vector<ii> raw;
	int n;
 
	void computeLog() {
		log.resize(n+1, -1);
		int p = 0, two_pow = 1;
		while (two_pow <= n) {
			log[two_pow] = p++;
			two_pow *= 2;
		}
		int prev = 0;
		for_(i, 1, n+1) {
			if (log[i] != -1) prev = log[i];
			else log[i] = prev;
		}
	}
 
	void buildTable() {
		int k = log[n]+1;
		st.resize(n, vector<ii> (k));
		for_(i, 0, n) st[i][0] = raw[i];
		for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1) 
			st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
	}
 
	public:
	void build(vector<ii> nums) {
		raw = nums;
		n = nums.size();
		computeLog();
		buildTable();
	}
 
	int mn(int l, int r) {
		if (l > r) swap(l, r);
		int p = log[r-l+1];
		return min(st[l][p], st[r - (1<<p) + 1][p]).second;
	}
};
 
SparseTable st;
vector<vi> adj;
vector<ii> tour;
vi tin, tout;
 
void dfs(int p, int d, int parent) {
	tin[p] = tour.size();
	tour.push_back({d, p});
	for (int i: adj[p]) if (i != parent) {
		dfs(i, d+1, p);
		tour.push_back({d, p});
	}
	
	tin[p] = tour.size()-1;
}
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q; cin >> n >> m >> q;
	adj.resize(n); tin.resize(n); tout.resize(n);
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	
	dfs(0, 0, 0);
	st.build(tour);
	
	vi nums(m);
	vector<multiset<int>> pos(n);
 
	for_(i, 0, m) {
		cin >> nums[i]; nums[i]--;
		pos[nums[i]].insert(i);
	}
	
	for_(i, 0, m-1) {
		pos[st.mn(tin[nums[i]], tin[nums[i+1]])].insert(i);
	}
	
	for_(_, 0, q) {
		int t; cin >> t;
		if (t == 1) {
			int i, v; cin >> i >> v;
			v -= 1; i -= 1;
			if (i > 0) {
				pos[st.mn(tin[nums[i]], tin[nums[i-1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i-1]])].find(i-1));
				pos[st.mn(tin[v], tin[nums[i-1]])].insert(i-1);
			}
			if (i < m-1) {
				pos[st.mn(tin[nums[i]], tin[nums[i+1]])].erase(pos[st.mn(tin[nums[i]], tin[nums[i+1]])].find(i));
				pos[st.mn(tin[v], tin[nums[i+1]])].insert(i);
			}
			
			pos[nums[i]].erase(pos[nums[i]].find(i));
			nums[i] = v;
			pos[nums[i]].insert(i);
		} else {
			int l, r, v; cin >> l >> r >> v;
			v -= 1; l -= 1; r -= 1;
			auto pt = pos[v].lower_bound(l);
			int ansl = -2, ansr = -2;
			if (pt != pos[v].end() and *pt <= r) {
				int idx = *pt;
				if (nums[idx] == v) ansl = ansr = idx;
				else if (idx < r) {
					ansl = idx; ansr = idx+1;
				}
			}
			
			cout << ansl+1 << " " << ansr+1 << endl;
		}
	}
 
	return 0;
}

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