Submission #1157514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157514		dombly	Tourism (JOI23_tourism)	C++20	100 / 100	754 ms	24136 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back
const int N = 1e5 + 69;
int n, m, q, c[N], ans[N], sz[N], top[N], pos[N], fenw[N];
int node, par[N], dep[N];
vector<int> g[N];
vector<pair<int, int>> qs[N];
set<array<int,3>> st;
void modify(int v, int val) {
	for (int i = v;i < N;i += (i & -i))
		fenw[i] += val;
}
int Get(int v) {
	int r = 0;
	for (int i = v;i > 0;i -= (i & -i))
		r += fenw[i];
	return r;
}
void dfs(int v, int p) {
	sz[v] = 1;
	par[v] = p;
	dep[v] = dep[p] + 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}
void hld(int v, int p, int tp) {
	pos[v] = ++node;
	top[v] = tp;
	int s = -1, mx = 0;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		if (sz[u] > mx) {
			mx = sz[u];
			s = u;
		}
	}
	if (s == -1)
		return;
	hld(s, v, tp);
	for (auto u : g[v]) {
		if (u == s || u == p)
			continue;
		hld(u, v, u);
	}
}
void Modify(int l, int r, int v) {
    if(l > r) swap(l,r);
    auto lb = st.lower_bound({l,0,0});
    vector<array<int,3>>vec;
    if(lb != st.begin()) {
        vec.pb(*prev(lb));
    }
    while(lb != st.end()) {
        array<int,3>u = *lb;
        if(u[0] > r) break;
        vec.pb(u);
        lb++;
    }
    for(auto [ll,rr,vv] : vec) {
        if(rr < l || ll > r) continue;
        modify(vv,-(min(rr,r) - max(ll,l) + 1));
        if(ll < l) st.insert({ll,l - 1,vv});
        if(rr > r) st.insert({r + 1,rr,vv});
        st.erase({ll,rr,vv});
    }
    modify(v,r - l + 1);
    st.insert({l,r,v});
}
void Change(int a, int b, int c) {
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]])
			swap(a, b);
		Modify(pos[top[a]], pos[a], c);
		a = par[top[a]];
	}
	Modify(pos[b], pos[a], c);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	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++) {
  		int l, r;
  		cin >> l >> r;
  		qs[r].push_back({l, i});
  	}
  	dfs(1, 0);
  	hld(1, 1, 1);
  	st.insert({1, n, N});
  	for (int i = 1;i <= m;i++) {
  		if (i > 1)
  			Change(c[i], c[i - 1], i - 1);
  		for (auto u : qs[i]) {
  			int l, ind;
  			tie(l, ind) = u;
  			if (l == i)
  				ans[ind] = 1;
  			else
  				ans[ind] = Get(N - 1) - Get(l - 1);
  		}
  	}
  	for (int i = 1;i <= q;i++)
  		cout << ans[i] << '\n';
	}
  return 0;
}

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