Submission #521338

#	Time	Username	Problem	Language	Result	Execution time	Memory
521338		Jasiekstrz	Construction of Highway (JOI18_construction)	C++17	100 / 100	388 ms	16120 KiB

construction

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int P=(1<<17);
int tab[N+10];
int que[N+10];
vector<int> e[N+10];
int par[N+10];
int dep[N+10];
int up[N+10];
int pre[N+10];
int post[N+10];
int pot;
pair<int,int> tr[2*P+10];
long long fen[P+10];
void upd(int x,pair<int,int> c)
{
	for(x+=pot-1;x>=1;x/=2)
		tr[x]=max(tr[x],c);
	return;
}
pair<int,int> read(int l,int r)
{
	pair<int,int> ans={0,1};
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=max(ans,tr[l++]);
		if(r%2==0)
			ans=max(ans,tr[r--]);
	}
	return ans;
}
void dfs_pre(int x)
{
	static int nr=0;
	pre[x]=++nr;
	dep[x]=dep[par[x]]+1;
	for(auto v:e[x])
		dfs_pre(v);
	post[x]=nr;
	return;
}
int g(int x)
{
	return read(pre[x],post[x]).se;
}
int lsb(int x)
{
	return x&(-x);
}
long long read_inv(int x)
{
	long long ans=0;
	for(;x>0;x-=lsb(x))
		ans+=fen[x];
	return ans;
}
void add_inv(int x,long long c)
{
	for(;x<=pot;x+=lsb(x))
		fen[x]+=c;
	return;
}
long long solve_inv(vector<tuple<int,int,int>> &vec)
{
	sort(vec.begin(),vec.end());
	long long ans=0;
	for(auto [a,b,c]:vec)
	{
		b=-b;
		ans+=read_inv(b-1)*c;
		add_inv(b,c);
	}
	for(auto [a,b,c]:vec)
		add_inv(-b,-c);
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>tab[i];
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		par[b]=a;
		que[i]=b;
	}
	dfs_pre(1);
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=2*pot;i++)
		tr[i]={0,1};
	for(int qi=1;qi<n;qi++)
	{
		vector<tuple<int,int,int>> vec;
		for(int x=par[que[qi]];x>0;)
		{
			int gr=g(x);
			//cerr<<qi<<" "<<x<<" "<<gr<<"\n";
			vec.push_back({tab[gr],-vec.size()-1,dep[x]-dep[up[gr]]});
			swap(x,up[gr]);
		}
		cout<<solve_inv(vec)<<"\n";
		upd(pre[que[qi]],{qi,que[qi]});
		up[que[qi]]=0;
	}
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84