Submission #342118

#	Time	Username	Problem	Language	Result	Execution time	Memory
342118		maskoff	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1390 ms	109804 KiB

treearray

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 3e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int up[N][20], timer;
int tin[N], tout[N];
int n, m, q, c[N];
vector<int> g[N];
set<int> s[N], all[N];
            
void dfs(int x, int pr) {
 	up[x][0] = pr;
 	tin[x] = timer++;
 	for (int i = 1; i <= 18; i++)
 		up[x][i] = up[up[x][i - 1]][i - 1];
 	for (int to : g[x])
 		if (to != pr)
 			dfs(to, x);
 	tout[x] = timer++;
}

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

int lca(int x, int y) {
 	if (upper(x, y)) return x;
 	if (upper(y, x)) return y;
 	for (int i = 18; i >= 0; i--)
 		if (!upper(up[x][i], y) && up[x][i])
 			x = up[x][i];
	return up[x][0];
}             

void update() {
 	int pos, val;
 	cin >> pos >> val;
 	
 	int p = c[pos];

 	all[p].erase(pos);
 	all[val].insert(pos);

 	c[pos] = val;
 	
 	if (m == 1) return;

 	if (pos == m) {
 		int v = lca(c[m - 1], p);
 	 	s[v].erase(m - 1);
 	 	v = lca(c[m - 1], c[m]);
 	 	s[v].insert(m - 1);
 	}

 	else if (pos == 1) {
 	 	int v = lca(p, c[2]);
 	 	s[v].erase(1);
 	 	v = lca(c[1], c[2]);
 	 	s[v].insert(1);

 	} else {
 	 	int v = lca(p, c[pos - 1]);
 	 	s[v].erase(pos - 1);
 	 	v = lca(c[pos], c[pos - 1]);
 	 	s[v].insert(pos - 1);
 	 	v = lca(c[pos + 1], p);
 	 	s[v].erase(pos);
 	 	v = lca(c[pos + 1], c[pos]);
 	 	s[v].insert(pos);
 	}
}

void get() {
	int l, r, v;
	cin >> l >> r >> v;
	auto pos = *s[v].upper_bound(l - 1);
	if (pos < r) {
		cout << pos << " " << pos + 1 << endl;
		return;		
 	}
 	pos = *all[v].upper_bound(l - 1);
 	if (pos <= r) {
 	 	cout << pos << " " << pos << endl;
 	 	return;
 	}
 	cout << "-1 -1\n";
}                              

int main() { 
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		s[i].insert(m + 1), all[i].insert(m + 1);
	for (int i = 1; i < n; i++) {
	 	int x, y;
	 	cin >> x >> y;
	 	g[x].pb(y);
	 	g[y].pb(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= m; i++) cin >> c[i];
	for (int i = 1; i <= m; i++)
		all[c[i]].insert(i);
	for (int i = 1; i < m; i++) 
		s[lca(c[i], c[i + 1])].insert(i);
	
	while (q--) {
   	int t;
   	cin >> t;
   	if (t == 1) update();
   	if (t == 2) get();
  }
  return 0;
}

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