Submission #585948

#	Time	Username	Problem	Language	Result	Execution time	Memory
585948		Zanite	Birthday gift (IZhO18_treearray)	C++17	100 / 100	739 ms	130932 KiB

treearray

// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

using pii	= pair<int, int>;

#define fi first
#define se second

const int maxN	= 2e5 + 5;
const int logN	= 21;

int n, m, q, a[maxN];

vector<int> adj[maxN];
int tin[maxN], tout[maxN], depth[maxN];
vector<int> Euler;

set<pii> seg[maxN];

struct SparseTable {
	int s;
	vector<vector<pii>> ST;

	void build() {
		s = Euler.size();

		ST.push_back(vector<pii>(0));
		for (auto i : Euler) {
			ST[0].push_back({depth[i], i});
		}

		for (int i = 1; i < logN; i++) {
			ST.push_back(vector<pii>(s));

			for (int j = 0; j <= s - (1 << i); j++) {
				ST[i][j] = min(ST[i-1][j], ST[i-1][j + (1 << (i-1))]);
			}
		}
	}

	pii query(int l, int r) {
		int d = r - l + 1;
		int t = 31 - __builtin_clz(d);

		return min(ST[t][l], ST[t][r - (1 << t) + 1]);
	}

	void print() {
		for (auto i : ST) {
			for (auto j : i) {
				printf("{%d, %d} ", j.fi, j.se);
			}
			printf("\n");
		}
	}
} TreeData;

void dfs(int cur, int par, int dpt) {
	Euler.push_back(cur);
	tin[cur] = Euler.size()-1;
	depth[cur] = dpt;

	for (auto nxt : adj[cur]) {
		if (nxt == par) continue;
		dfs(nxt, cur, dpt+1);
		Euler.push_back(cur);
	}

	tout[cur] = Euler.size()-1;
}

int LCA(int x, int y) {
	//cerr << "LCA " << x << " " << y << '\n';
	if (x == 0) return y;
	if (y == 0) return x;
	if (tin[x] > tin[y]) swap(x, y);
	return TreeData.query(tin[x], tin[y]).se;
}

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int u, v, i = 1; i < n; i++) {
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0, 0);
	TreeData.build();

	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[i]);
	}

	// create segments
	for (int i = 1; i <= m; i++) {
		seg[a[i]].insert({i, i});
	}
	for (int i = 1; i < m; i++) {
		seg[LCA(a[i], a[i+1])].insert({i, i+1});
	}

	for (int typ, pos, l, r, v, i = 1; i <= q; i++) {
		scanf("%d", &typ);

		if (typ == 1) {
			scanf("%d %d", &pos, &v);

			seg[a[pos]].erase({pos, pos});
			if (pos > 1) {seg[LCA(a[pos-1], a[pos])].erase({pos-1, pos});}
			if (pos < m) {seg[LCA(a[pos], a[pos+1])].erase({pos, pos+1});}

			a[pos] = v;
			
			seg[a[pos]].insert({pos, pos});
			if (pos > 1) {seg[LCA(a[pos-1], a[pos])].insert({pos-1, pos});}
			if (pos < m) {seg[LCA(a[pos], a[pos+1])].insert({pos, pos+1});}

		} else {
			scanf("%d %d %d", &l, &r, &v);
			pii ans = {-1, -1};
			
			auto it = seg[v].lower_bound({l, -1});
			if (it != seg[v].end()) {
				int xl, xr;
				tie(xl, xr) = *it;
				if (l <= xl && xl <= r && l <= xr && xr <= r) ans = *it;
			}

			printf("%d %d\n", ans.fi, ans.se);

		}
	}
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
treearray.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &typ);
      |   ~~~~~^~~~~~~~~~~~
treearray.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |    scanf("%d %d", &pos, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:121:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |    scanf("%d %d %d", &l, &r, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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