제출 #643761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643761		ymm	Birthday gift (IZhO18_treearray)	C++17	100 / 100	3715 ms	95348 KiB

treearray

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 18;
const int S = 512;
int val[N], node[N];
vector<int> A[N];
vector<pii> ord;
int st[N];
pii rmq[lg+1][2*N];
int n, m, q;

__attribute__((optimize("O3,unroll-loops"),target("avx")))
int get_ind(int l, int r, int x, bool cnt)
{
	int *val = cnt? ::val: node;
	for (int i = l; i < r; i += S) {
		int j = min(i+S, r);
		int y = 0;
		Loop (k,i,j)
			y |= -(val[k] == x);
		if (y) {
			Loop (k,i,j)
				if (val[k] == x)
					return k;
		}
	}
	return -1;
}

void dfs(int v, int p, int h)
{
	st[v] = ord.size();
	ord.push_back({h, v});
	for (int u : A[v]) {
		if (u != p) {
			dfs(u, v, h+1);
			ord.push_back({h, v});
		}
	}
}

void rmq_init()
{
	int n = ord.size();
	Loop (i,0,n)
		rmq[0][i] = ord[i];
	Loop (i,0,lg)
		for (int j = 0; j + (2<<i) <= n; ++j)
			rmq[i+1][j] = min(rmq[i][j], rmq[i][j+(1<<i)]);
}
int get_anc(int v, int u)
{
	v = st[v]; u = st[u];
	if (v > u) swap(v, u);
	++u;
	int l = __lg(u - v);
	return min(rmq[l][v], rmq[l][u-(1<<l)]).second;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m >> q;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs(0, -1, 0);
	rmq_init();
	Loop (i,0,m) {
		cin >> node[i];
		--node[i];
	}
	Loop (i,0,m-1)
		val[i] = get_anc(node[i], node[i+1]);
	Loop (_,0,q) {
		//Loop (i,0,m-1) cout << val[i]+1 << ' '; cout << '\n';
		int t;
		cin >> t;
		if (t == 1) {
			int i, v;
			cin >> i >> v;
			--i; --v;
			node[i] = v;
			if (i > 0)
				val[i-1] = get_anc(node[i-1], node[i]);
			if (i < m-1)
				val[i] = get_anc(node[i], node[i+1]);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			--l; --r; --v;
			int ans = get_ind(l, r, v, 1);
			if (ans < 0) {
				ans = get_ind(l, r+1, v, 0);
				if (ans < 0)
					cout << "-1 -1\n";
				else
					cout << ans+1 << ' ' << ans+1 << '\n';
			} else {
				cout << ans+1 << ' ' << ans+2 << '\n';
			}
		}
	}
}

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