Submission #828810

#	Time	Username	Problem	Language	Result	Execution time	Memory
828810		MohamedAhmed04	Construction of Highway (JOI18_construction)	C++14	100 / 100	217 ms	21908 KiB

construction

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int a[MAX] , b[MAX] ;
int n ;

vector< vector<int> >adj(MAX) ;

int bit[MAX] ;
stack< pair<int , int> >adds ;

void add(int i , int x)
{
	adds.push({i , x}) ;
	for(; i <= n ; i += (i & (-i)))
		bit[i] += x ;
}

int get(int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

int query(int l , int r)
{
	return (get(r) - get(l-1)) ;
}

void Clear()
{
	while(adds.size())
	{
		pair<int , int>p = adds.top() ;
		adds.pop() ;
		int i = p.first , x = p.second ;
		for(; i <= n ; i += (i & (-i)))
			bit[i] -= x ;
	}
}

void compress()
{
	vector<int>v ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back(arr[i]) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		arr[i] = lower_bound(v.begin() , v.end() , arr[i]) - v.begin() ;
		arr[i]++ ;
	}
}

int sz[MAX] , head[MAX] , P[MAX] ;
int in[MAX] , out[MAX] ;
int tim = 0 ;

void dfs(int node)
{
	sz[node] = 1 ;
	for(auto &child : adj[node])
	{
		P[child] = node ;
		dfs(child) ;
		sz[node] += sz[child] ;
		if(sz[child] > sz[adj[node][0]])
			swap(child , adj[node][0]) ;
	}
}

void hld(int node)
{
	in[node] = ++tim ;
	for(auto &child : adj[node])
	{
		if(child == adj[node][0])
			head[child] = head[node] ;
		else
			head[child] = child ;
		hld(child) ;
	}
	out[node] = tim ;
}

vector< array<int , 3> >v[MAX] ;
vector< pair<int , int> >vp ;

long long solve(int node)
{
	Clear() ;
	long long ans = 0 ;
	int now = node ;
	while(now)
	{
		vp.clear() ;
		while(v[head[now]].size() && v[head[now]].back()[1] < in[now])
			vp.emplace_back(v[head[now]].back()[2] , v[head[now]].back()[1] - v[head[now]].back()[0] + 1) , v[head[now]].pop_back() ;
		if(v[head[now]].size() && v[head[now]].back()[0] <= in[now])
		{
			int l = v[head[now]].back()[0] , r = v[head[now]].back()[1] , x = v[head[now]].back()[2] ;
			vp.emplace_back(x , in[now] - l + 1) ;
			v[head[now]].pop_back() ;
			v[head[now]].push_back({in[now]+1 , r , x}) ;
		}
		v[head[now]].push_back({in[head[now]] , in[now] , arr[node]}) ;
		reverse(vp.begin() , vp.end()) ;
		for(auto &p : vp)
			ans += 1ll * p.second * get(p.first-1) , add(p.first , p.second) ;
		now = P[head[now]] ;
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= n-1 ; ++i)
	{
		cin>>a[i]>>b[i] ;
		adj[a[i]].push_back(b[i]) ;
	}
	compress() ;
	head[1] = 1 ;
	dfs(1) ;
	hld(1) ;
	for(int i = 1 ; i <= n-1 ; ++i)
		cout<<solve(b[i])<<"\n" ;
	return 0 ;
}		

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