Submission #1142240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142240		monkey133	Tourism (JOI23_tourism)	C++20	100 / 100	297 ms	26812 KiB

tourism

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef int  ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const INF = 1e9;
ll n,m, q, hld_label = 0;
ll c[100005], dep[100005], siz[100005], heavyp[100005], par[100005], in[100005], out[100005], ans[100005];
vector<pi> que[100005];
vector<ll> adj[100005];
set<pii> seg[100005];
vector<ll> fenwick(100005,0);

ll ps(ll i)
{
	if (i==0) return 0;
	ll sum=0;
	while (i>0)
	{
		sum+=fenwick[i];
		i-=i&(-i);
	}
	return sum;
}
void update(ll i, ll v)
{
	if (i==0) return;
	while (i<=100005)
	{
		fenwick[i]+=v;
		i+=i&(-i);
	}
}

void dfs(ll x = 1, ll p = -1)
{
	siz[x] = 1;
	for (ll u: adj[x]) if (p!=u)
	{
		dep[u] = dep[x] + 1;
		par[u] = x;
		dfs(u, x);
		siz[x] += siz[u];
	}
}

void dfs_hld(ll x = 1, ll p = -1)
{
	in[x] = ++hld_label;
	for (ll i=1; i<adj[x].size(); ++i) if (adj[x][i]!=p && (adj[x][0]==p || siz[adj[x][0]] < siz[adj[x][i]])) swap(adj[x][0], adj[x][i]);
	for (ll i=0; i<adj[x].size(); ++i)
	{
		if (adj[x][i]==p) continue;
		if (i==0) heavyp[adj[x][i]] = heavyp[x];
		else heavyp[adj[x][i]] = adj[x][i];
		dfs_hld(adj[x][i], x);
	}
	out[x] = hld_label;
}


void add(ll from, ll to, ll heavy, ll t)
{
	//for (pii u: seg[heavy]) show3(u.f.f, u.f.s, u.s);
	auto it = seg[heavy].ub(mp(mp(dep[from], INF), INF));
	if (it!=seg[heavy].begin()) it--;
	vector<pii> push;
	push.pb(mp(mp(dep[from], dep[to]), t));
	while (it!=seg[heavy].end() && it->f.f <= dep[to])
	{
		pii now = *it;
		it = seg[heavy].erase(it);
		ll lo = max(now.f.f, dep[from]), hi = min(now.f.s, dep[to]);
		update(now.s, - (hi - lo + 1));
		if (now.f.f < dep[from]) push.pb(mp(mp(now.f.f, dep[from]-1), now.s));
		if (now.f.s > dep[to]) push.pb(mp(mp(dep[to] + 1, now.f.s), now.s));
		
		
	}
	update(t, dep[to] - dep[from] + 1);
	for (pii u: push) seg[heavy].insert(u);
}


void insert(ll a, ll b, ll t)
{
	while (heavyp[a] != heavyp[b])
	{
		if (dep[heavyp[a]] < dep[heavyp[b]]) swap(a, b);
		// do range op
		//show3(heavyp[a], a, heavyp[a]);
		add(heavyp[a], a, heavyp[a], t);
		a = par[heavyp[a]];
	}
	if (in[a] > in[b]) swap(a,b);
	//show3(a, b, heavyp[a]);
	add(a, b, heavyp[a], t);
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m >> q;
	for (ll i=0; i<n-1; ++i)
	{
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for (ll i=1; i<=m; ++i) cin >> c[i];
	for (ll i=0; i<q; ++i)
	{
		ll l, r;
		cin >> l >> r;
		que[r].pb(mp(l, i));
	}
	par[1] = -1, dep[1] = 0, heavyp[1] = 1;
	dfs();
	dfs_hld();
	for (ll i=1; i<=m; ++i)
	{
		//show(i);
		// change path from c[i-1] to c[i] to i-1
		if (i > 1) insert(c[i-1], c[i], i-1);
		//for (ll i=1; i<=m; ++i) show2(i, ps(i) - ps(i-1));
		// change c[i] to i
		insert(c[i], c[i], i);
		//for (ll i=1; i<=m; ++i) show2(i, ps(i) - ps(i-1));
		for (pi u: que[i]) ans[u.s] = ps(i) - ps(u.f - 1);
	}
	for (ll i=0; i<q; ++i) cout << ans[i] << endl;
	
	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