Submission #235738

#	Time	Username	Problem	Language	Result	Execution time	Memory
235738		MvC	Construction of Highway (JOI18_construction)	C++14	100 / 100	773 ms	25076 KiB

construction

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int x,y,i,n,up[nmax][20],tin[nmax],tout[nmax],tt,ex[nmax],ey[nmax],c[nmax],d,z,u,j,lvl[nmax],sz,nr,lc,fw[nmax];
ll rs;
vector<int>a[nmax];
pair<int,int>st[4*nmax],pr;
vector<int>vc;
vector<pair<int,int> >vec;
void ufw(int i,int v)
{
	for(;i>=1;i-=i&(-i))fw[i]+=v;
}
int qfw(int i)
{
	int ans=0;
	for(;i<=sz;i+=i&(-i))ans+=fw[i];
	return ans;
}
void dfs(int x,int p)
{
	lvl[x]=lvl[p]+1;
    tin[x]=++tt;
    up[x][0]=p;
    for(int i=1;i<17;i++)up[x][i]=up[up[x][i-1]][i-1];
    for(int i=0;i<(int)a[x].size();i++)dfs(a[x][i],x);
    tout[x]=tt;
}
int anc(int x,int y)
{
    return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
    if(anc(x,y))return x;
    if(anc(y,x))return y;
    for(int i=16;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
    return up[x][0];
}
void upd(int nod,int l,int r,int p,pair<int,int>v)
{
	if(l==r)
	{
		st[nod]=v;
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=max(st[2*nod],st[2*nod+1]);
}
pair<int,int> qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return mkp(0,0);
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return max(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>c[i],vc.pb(c[i]);
	sort(all(vc));
	vc.resize(unique(all(vc))-vc.begin());
	sz=(int)vc.size();
	for(i=1;i<=n;i++)c[i]=lower_bound(all(vc),c[i])-vc.begin()+1;
	for(i=1;i<n;i++)
	{
		cin>>ex[i]>>ey[i];
		a[ex[i]].pb(ey[i]);
	}
	dfs(1,1);
	for(i=1;i<n;i++)
	{
		x=ex[i],y=ey[i];
		vec.clear();
		z=1,rs=0;
		while(1)
		{
			pr=qry(1,1,n,tin[z],tout[z]);
			if(!pr.fr)break;
			u=pr.sc;
			lc=lca(y,u);
			nr=qfw(c[u]+1);
			rs+=1LL*nr*1LL*(lvl[lc]-lvl[z]+1);
			ufw(c[u],lvl[lc]-lvl[z]+1);
			vec.pb(mkp(c[u],lvl[lc]-lvl[z]+1));
			if(lc==x)break;
			d=lvl[y]-lvl[lc]-1;
			z=y;
			for(j=16;j>=0;j--)if(d&(1<<j))z=up[z][j];
		}
		upd(1,1,n,tin[y],mkp(i,y));
		for(j=0;j<(int)vec.size();j++)ufw(vec[j].fr,-vec[j].sc);
		cout<<rs<<'\n';
	}
	return 0;
}

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