Submission #1037164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037164		1L1YA	Construction of Highway (JOI18_construction)	C++17	100 / 100	371 ms	28952 KiB

construction

//1L1YA

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

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1e5+11;
const int lg=19;

int n,t=1,a[N],h[N],sz[N],st[N],up[N],fen[N],head[N],seg[N<<2],par[lg][N];
vector<int> G[N];
vector<pii> E(N);

void shift(int id){
	if(!seg[id])	return;
	seg[lc]=seg[id];seg[rc]=seg[id];
	seg[id]=0;
}

void update(int ql,int qr,int val,int id=1,int l=1,int r=n+1){
	if(qr<=l || ql>=r)	return;
	if(ql<=l && r<=qr){
		seg[id]=val;
		return;
	}
	shift(id);
	update(ql,qr,val,lc,l,mid);
	update(ql,qr,val,rc,mid,r);
}

int get(int pos,int id=1,int l=1,int r=n+1){
	if(r-l==1)	return seg[id];
	shift(id);
	if(pos<mid)	return get(pos,lc,l,mid);
	return get(pos,rc,mid,r);
}

bool cmp(int x,int y){
	return sz[x]>sz[y];
}

void dfsset(int v){
	sz[v]=1;
	for(int u: G[v]){
		h[u]=h[v]+1;
		dfsset(u);
		sz[v]+=sz[u];
	}
	sort(all(G[v]),cmp);
}

void dfs_hld(int v){
	st[v]=t++;
	if(SZ(G[v]))	head[G[v][0]]=head[v];
	for(int u: G[v])	dfs_hld(u);
}

void update_path(int v,int x){
	while(head[v]!=1){
		update(st[head[v]],st[v]+1,x);
		v=par[0][head[v]];
	}
	update(1,st[v]+1,x);
}

int jump(int v,int k){
	if(k<0)	return v;
	for(int i=0;i<lg;i++)
		if(k>>i & 1)
			v=par[i][v];
	return v;
}

void upd(int x,int y){
	for(x=n-x;x<=n;x+=x&-x)	fen[x]+=y;
}

int gett(int x){
	int ans=0;
	for(x=n-x;x;x-=x&-x)	ans+=fen[x];
	return ans;
}

int main(){
	FastIO

	cin >> n;
	vector<int> comp;
	for(int i=1;i<=n;i++)	cin >> a[i],comp.Pb(a[i]);
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	for(int i=1;i<=n;i++)	a[i]=lower_bound(all(comp),a[i])-comp.begin();
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		par[0][v]=u;
		G[u].Pb(v);
		E[i]={u,v};
	}
	for(int i=1;i<lg;i++)
		for(int v=1;v<=n;v++)
			par[i][v]=par[i-1][par[i-1][v]];
	dfsset(1);
	for(int i=1;i<=n;i++)	head[i]=i;
	dfs_hld(1);
	update_path(1,1);
	up[1]=1;
	for(int i=1;i<n;i++){
		int u=E[i].F,v=E[i].S;
		vector<pii> vc;
		while(u){
			int w=get(st[u]);
			vc.Pb({w,h[u]-h[up[w]]+1});
			int p=jump(w,h[w]-h[u]-1);
			u=par[0][up[w]];
			up[w]=p;
		}
		reverse(all(vc));
		ll ans=0;
		for(auto [x,y]: vc)	ans+=(ll)y*gett(a[x]+1),upd(a[x],y);
		cout << ans << endl;
		for(auto [x,y]: vc)	upd(a[x],-y);
		up[v]=1;
		update_path(v,v);
	}

	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void update(int, int, int, int, int, int)':
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:54:24: note: in expansion of macro 'mid'
   54 |  update(ql,qr,val,lc,l,mid);
      |                        ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:55:22: note: in expansion of macro 'mid'
   55 |  update(ql,qr,val,rc,mid,r);
      |                      ^~~
construction.cpp: In function 'int get(int, int, int, int)':
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:61:9: note: in expansion of macro 'mid'
   61 |  if(pos<mid) return get(pos,lc,l,mid);
      |         ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:61:34: note: in expansion of macro 'mid'
   61 |  if(pos<mid) return get(pos,lc,l,mid);
      |                                  ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:62:20: note: in expansion of macro 'mid'
   62 |  return get(pos,rc,mid,r);
      |                    ^~~

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