Submission #728268

#	Time	Username	Problem	Language	Result	Execution time	Memory
728268		penguin133	Tourism (JOI23_tourism)	C++17	100 / 100	1169 ms	65976 KiB

tourism

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

int sz[1000005], head[1000005], par[20][100005], dep[1000005], S[1000005], E[1000005];
int up[1000005];
vector<int>v[1000005];
int n, m, q;
vector<pii>adj;
int hello = 1;
void dfs(int x, int p, int d){
	dep[x] = d;
	up[x] = p;
	sz[x] = 1;
	for(auto i : v[x]){
		if(i == p)continue;
		dfs(i, x, d + 1);
		sz[x] += sz[i];
	}
}


struct node{
	int s,e,m,val, lazy = 0, mc = 0;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		val = 0, mc = e - s + 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void propo(){
		if(lazy){
			val += lazy;
			if(s != e)l->lazy += lazy, r->lazy += lazy;
			lazy = 0;
		}
	}
	
	pi comb(pi a, pi b){
		pi ans;
		ans.fi = min(a.fi, b.fi);
		if(a.fi == b.fi)ans.se = a.se + b.se;
		else ans.se = (a.fi < b.fi ? a.se : b.se);
		return ans;
	}
	
	void upd(int a, int b, int c){
		//cerr << "UPD " << a << " " << b << " " << c << '\n';
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			//val = l->val + r->val;
			val = min(l->val, r->val);
			if(l->val == r->val)mc = l->mc + r->mc;
			else mc = (l->val < r->val ? l->mc : r->mc);
		}
	}
	pi query(int a, int b){
		propo();
		if(a == s && b == e)return {val, mc};
		else if( b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return comb(l->query(a, m), r->query(m+1, b));
	}
}*root;
int cnt = 1;
void dfs2(int x, int h, int par){
	S[x] = cnt++;
	head[x] = h;
	int maxi = 0, in = -1;
	for(auto i : v[x]){
		if(i == par)continue;
		if(maxi < sz[i])maxi = sz[i], in = i;
	}
	for(auto i : v[x]){
		if(i == par)continue;
		if(i == in)dfs2(i, h, x);
	}
	for(auto i : v[x]){
		if(i != par && i != in)dfs2(i, i, x);
	}
	E[x] = cnt-  1;
}


/*
int query(int a, int b) {
    int res = 0;
    for (; head[a] != head[b]; b = up[head[b]]) {
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);
        int cur_heavy_path_max = root->query(S[head[b]], S[b]);
        res += cur_heavy_path_max;
    }
    if (dep[a] > dep[b])
        swap(a, b);
    res += root->query(S[a], S[b]);
    return res;
}
void st(int x, int a){
	if(S[x] <= S[hello] && E[hello] <= E[x]){
		int in = -1;
		for(auto i : v[x]){
			if(S[i] <= S[hello] && E[hello] <= E[i] && S[i] > S[x])in = i;
		}
		root->upd(1, n, a);
		if(in != -1)root->upd(S[in], E[in], -a);
	}
	else root->upd(S[x], E[x], a);
}
int qu(int x){
	int res=  0;
	if(S[x] <= S[hello] && E[hello] <= E[x]){
		int in = -1;
		for(auto i : v[x]){
			if(S[i] <= S[hello] && E[hello] <= E[i] && S[i] > S[x])in = i;
		}
		root->propo();
		res = root->val;
		if(in != -1)res -= root->query(S[in], E[in]);
		return res;
	}
	else return root->query(S[x], E[x]);
}
*/
int C[100005], ans[100005];
vector <pi> qu[100005];
set <pii> s;

int ft[100005];

void upd(int p, int v){
	for(;p<=m;p+=(p & -p))ft[p] += v;
}

int qry(int p){
	int res = 0;
	for(;p;p-=(p & -p))res += ft[p];
	return res;
}

void ins(int l, int r, int i){
	auto it = s.upper_bound({l-1, {1e9, 1e9}});
	vector <pii> sad, nw;
	if(it != s.begin()){
		it--;
		pii tmp = *it;
		if(tmp.se.fi < l)it++;
		else{
			nw.push_back({tmp.fi, {l - 1, tmp.se.se}});
			int x = tmp.se.se;
			if(tmp.se.fi > r){
				nw.push_back({r+1, {tmp.se.fi, tmp.se.se}});
			}
			upd(x, - (min(r, tmp.se.fi) - l + 1));
			sad.push_back(tmp);
			it++;
		}
	}
	while(it != s.end()){
		pii tmp = *it;
		if(tmp.fi > r)break;
		if(tmp.se.fi > r){
			nw.push_back({r+1, {tmp.se.fi, tmp.se.se}});
			int x = tmp.se.se;
			upd(x, -(r - tmp.fi + 1));
			sad.push_back(tmp);
			break;
		}
		sad.push_back(tmp);
		int x = tmp.se.se;
		upd(x, - (tmp.se.fi - tmp.fi + 1));
		it++;
	}
	s.insert({l, {r, i}});
	upd(i, r - l + 1);
	for(auto j : sad)s.erase(j);
	for(auto j : nw)s.insert(j);
}

void chng(int a, int b, int c) {
    for (; head[a] != head[b]; b = up[head[b]]) {
		//cerr << a << " " << b << " " << head[a] << " " << head[b] << '\n';
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);
       // root->upd(S[head[b]], S[b], c);
       ins(S[head[b]], S[b], c);
    }
    if (dep[a] > dep[b])
        swap(a, b);
    //root->upd(S[a], S[b], c);
    ins(S[a], S[b], c);
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> q;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=m;i++)cin >> C[i];
	root= new node(1, n);
	dfs(1, -1, 1);
	dfs2(1, 1, -1);
	for(int i=1;i<=q;i++){
		int a, b; cin >> a >> b;
		qu[b].push_back({a, i});
	}
	for(auto [i, j] : qu[1])ans[j] = 1;
	s.insert({1, {n, 1}});
	upd(1, n);
	for(int i=2;i<=m;i++){
		chng(C[i], C[i-1], i);
		for(auto [j, k] : qu[i]){
			ans[k] = n - qry(j);
		}
	}
	for(int i=1;i<=q;i++)cout << max(1ll, ans[i]) << '\n';
}

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