제출 #1214180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214180		k1r1t0	Tourism (JOI23_tourism)	C++20	0 / 100	383 ms	16200 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int N = 110000;
const int LOGN = 20;

int n, m, q, c[N], ql[N], qr[N], ans[N], sub[N], tin[N], tout[N], tcur = 0, head[N], par[N], ff[N];
vector<int> g[N], qq[N];

void dfs(int v = 1, int p = -1, int h = 1) {
	par[v] = p;
	head[v] = h;
	tin[v] = ++tcur;
	if (!g[v].empty()) {
		if (g[v][0] == p)
			swap(g[v][0], g[v].back());
		for (int i = 1; i < (int) g[v].size(); i++)
			if (g[v][i] != p && sub[g[v][i]] > sub[g[v][0]])
				swap(g[v][0], g[v][i]);
		for (int u : g[v]) if (u != p)
			dfs(u, v, (u == g[v][0] ? h : u));
	}
	tout[v] = tcur;
}

void pre(int v = 1, int p = -1) {
	sub[v] = 1;
	for (int u : g[v]) if (u != p) {
		pre(u, v);
		sub[v] += sub[u];
	}
}

void upd(int k, int x) {
	for (; k <= m; k += k & -k)
		ff[k] += x;
}

int get(int k) {
	int ans = 0;
	for (; k >= 1; k -= k & -k)
		ans += ff[k];
	return ans;
}

set<array<int, 3>> lr;

void upd_seg(int l, int r, int k) {
	while (true) {
		auto it = lr.lower_bound({l, 0, 0});
		if (it == lr.end() || (*it)[1] > r)
			break;
		auto [l2, r2, k2] = *it;
		lr.erase(it);
		int cnt = max(max(l, l2) - min(r, r2) + 1, 0);
		upd(k2, -cnt);
		if (l2 < l) lr.insert({l2, l - 1, k2});
		if (r < r2) lr.insert({r + 1, r2, k2});
	}
	upd(k, r - l + 1);
	lr.insert({r, l, k});
}

int cnt(int k) {
	return get(m) - get(k - 1);
}

bool is_anc(int u, int v) {
	return tin[u] <= tin[v] && tin[v] <= tout[u];
}

void upd(int u, int v, int k) {
	for (int _ = 0; _ < 2; _++) {
		while (!is_anc(head[u], v)) {
			upd_seg(tin[head[u]], tin[u], k);
			u = par[head[u]];
		}
		swap(u, v);
	}
	if (!is_anc(u, v))
		swap(u, v);
	assert(is_anc(u, v)); //WTF???
	if (u != v)
		upd_seg(tin[u] + 1, tin[v], k);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= m; i++)
		cin >> c[i];
	for (int i = 1; i <= q; i++)
		cin >> ql[i] >> qr[i];
	pre();
	dfs();
	for (int i = 1; i <= q; i++)
		qq[qr[i]].push_back(i);
	for (int i = 2; i <= m; i++) {
		upd(c[i - 1], c[i], i - 1);
		for (int k : qq[i])
			ans[k] = cnt(ql[k]);
	}
	for (int i = 1; i <= q; i++)
		cout << ans[i] + 1 << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41