Submission #999242

#	Time	Username	Problem	Language	Result	Execution time	Memory
999242		Dzadzo	Tourism (JOI23_tourism)	C++17	100 / 100	701 ms	54212 KiB

tourism

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 100005
using namespace std;
set <pair<int,pii>> myset;
int bit[MAXN+1];
vvi P(MAXN+1,vi(20));
void add(int idx,int delta){
	for (;idx<=MAXN;idx+=idx&-idx)bit[idx]+=delta;
}
int get(int idx){
	int res=0;
	for (;idx>0;idx-=idx&-idx)res+=bit[idx];
	return res;
}
int n;
void update(int l,int r,int val){
	if(l>r)return;
	if (r>n)return;
	if (l<=0)return;
	auto it=myset.lower_bound({l,{0,0}});
	add(val,r-l+1);
	if ((*it).F!=l){
		it--;
		if ((*it).S.F<r){
			add((*it).S.S,-((*it).S.F-l+1));
			myset.insert({(*it).F,{l-1,(*it).S.S}});
			myset.erase(*it);
		}else if ((*it).S.F>=r){
			add((*it).S.S,-(r-l+1));
			myset.insert({(*it).F,{l-1,(*it).S.S}});
			if ((*it).S.F!=r)
			myset.insert({r+1,{(*it).S.F,(*it).S.S}});
			myset.erase(*it);
			myset.insert({l,{r,val}});
			return;
		}		
	}
	it=myset.lower_bound({l,{0,0}});
	vector <pair <int,pii>> del;
	for (;;it++){
		if (it==myset.end())break;
		if ((*it).F>r)break;

		del.pb(*it);
		if ((*it).S.F>r){
			add((*it).S.S,-(r-((*it).F)+1));
			myset.insert({r+1,{(*it).S.F,(*it).S.S}});
			break;
		}else add((*it).S.S,-((*it).S.F-(*it).F+1));		
	}
	myset.insert({l,{r,val}});
	for (auto x:del)myset.erase(x);
}
vvi adj(MAXN+1);
vi s(MAXN+1),tin(MAXN+1),tout(MAXN+1),dep(MAXN+1),par(MAXN+1);
int timer=0;
void dfs(int v,int p){
	tin[v]=++timer;
	par[v]=p;
	s[v]=1;
	P[v][0]=p;
	for (int i=1;i<20;i++)P[v][i]=P[P[v][i-1]][i-1];
	dep[v]=dep[par[v]]+1;
	for (int to:adj[v])if(to!=p)dfs(to,v),s[v]+=s[to];
	tout[v]=++timer;
}
vp T(4*MAXN+1);
vi c(MAXN+1);
void build(int v,int tl,int tr){
	if (tl==tr)T[v]={tin[c[tl]],tout[c[tl]]};else{
		int tm=(tl+tr)/2;
		build(v*2,tl,tm);
		build(v*2+1,tm+1,tr);
		T[v]={min(T[2*v].F,T[2*v+1].F),max(T[2*v].S,T[2*v+1].S)};
	}
}
pii gettime(int v,int tl,int tr,int l,int r){
	if (l>r)return {INF,0};
	if (tl==l && tr==r)return T[v];
	int tm=(tl+tr)/2;
	pii L=gettime(v*2,tl,tm,l,min(r,tm));
	pii R=gettime(v*2+1,tm+1,tr,max(l,tm+1),r);
	return {min(L.F,R.F),max(L.S,R.S)};
}

vi head(MAXN+1),ind(MAXN+1);int cnt;
void decomp(int v,int h){
	head[v]=h;
	ind[v]=++cnt;
	pii best={0,0};
	for (int to:adj[v])if (to!=par[v])best=max(best,{s[to],to});
	if(!best.S)return;
	decomp(best.S,h);
	for (int to:adj[v])if(to!=best.S && to!=par[v])decomp(to,to);
}
void up(int a,int b,int val){
	for (;head[a]!=head[b];b=par[head[b]]){
		if (dep[head[a]]>dep[head[b]])swap(a,b);
		update(ind[head[b]],ind[b],val);
	}
	if (dep[a]>dep[b])swap(a,b);
	update(ind[a],ind[b],val);
}
int calc(int v,int t1,int t2){
	if (t1>=tin[v] && t2<=tout[v])return dep[v]-1;
	int res=v;
	for (int bit=19;bit>=0;bit--){
		if (!P[res][bit])continue;
		if (t1<tin[P[res][bit]] || t2>tout[P[res][bit]])res=P[res][bit];
	}
	return dep[res]-2;
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int m,q;
	cin>>n>>m>>q;
	for (int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for (int i=1;i<=m;i++)cin>>c[i];
	dfs(1,0);
	build(1,1,m);
	decomp(1,1);
	myset.insert({1,{n,100001}});add(100001,n);
	vvp Q(MAXN+1);
	for (int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		Q[l].pb({r,i});
	}
	int ans[q+1];
	for (int l=m;l>=1;l--){
		up(c[l],1,l);
		for (auto &[r,id]:Q[l]){
			pii x=gettime(1,1,m,l,r);
			ans[id]=get(r)-get(l-1)-calc(c[l],x.F,x.S);
		}
	}
	for (int i=1;i<=q;i++)cout<<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