Submission #102629

#	Time	Username	Problem	Language	Result	Execution time	Memory
102629		scanhex	Construction of Highway (JOI18_construction)	C++17	100 / 100	1328 ms	30960 KiB

construction

#include <vector>
#include <iostream>
#include <random>
#include <cassert>
#include <tuple>
#include <algorithm>

using namespace std;
using nagai = long long;
#define sz(x) int((x).size())

const int LG=17;
const int N=1<<LG;
int mn[2*N];
int mx[2*N];
int psh[2*N];
void push1(int u){
	if(psh[u]){
		psh[u*2+1]=psh[u*2]=psh[u];
		mn[u*2+1]=mn[u*2]=mx[u*2]=mx[u*2+1]=psh[u];
		psh[u]=0;
	}
}
void push(int u){
	for(int i=LG;i>0;--i)
		push1(u>>i);
}
void upd(int u){
	mn[u]=min(mn[u*2+1],mn[u*2]);
	mx[u]=max(mx[u*2],mx[u*2+1]);
}
void st(int u,int l,int r,int ql,int qr,int v){
	if(l>=qr||ql>=r)return;
	if(ql<=l&&r<=qr){
		 psh[u]=mn[u]=mx[u]=v;
		 return;
	}
	push1(u);
	int m=(l+r)/2;
	st(u*2,l,m,ql,qr,v);
	st(u*2+1,m,r,ql,qr,v);
	upd(u);
}
int getr(int u,int l,int r,int ql,int v=-1){
	if(u==1){
		push(ql+N);
		v=mn[ql+N];
	}
	if(v<mn[u]||v>mx[u])return l;
	if(mn[u]==mx[u])
		return r;
	push1(u);
	int m=(l+r)/2;
	if(m<=ql)return getr(u*2+1,m,r,ql,v);
	int kek=getr(u*2,l,m,ql,v);
	if(kek==m){
		return getr(u*2+1,m,r,ql,v);
	}
	return kek;
}
int n;
int C[N];
vector<int>g[N];
vector<int>ch[N];
int sz[N];
void d1(int u,int p=-1){
	sz[u]=1;
	for(int v:g[u]){
		if(v==p)continue;
		d1(v,u);
		sz[u]+=sz[v];
		ch[u].push_back(v);
		if(sz[v]>sz[ch[u][0]])
			swap(ch[u].back(),ch[u].front());
	}
}
int tin[N];
int tot=0;
int top[N];
int par[N];
void d2(int u){
	tin[u]=tot++;
	for(int v:ch[u]){
		par[v]=u;
		top[v]=v==ch[u][0]?top[u]:v;
		d2(v);
	}
}
void st(int u,int col){
	while(true){
		int tp=top[u];
		st(1,0,N,tin[tp],tin[u]+1,col);
		if(tp==0)return;
		u=par[tp];
	}
}
vector<pair<int,int>>glob;
void gt1(int l,int r){
	while(true){
		int kek=getr(1,0,N,l);
		int v=mn[N+l];
		if(kek>=r){
			glob.emplace_back(r-l,v);
			return;
		}
		glob.emplace_back(kek-l,v);
		l=kek;
	}
}
void gt(int u){
	glob.clear();
	vector<pair<int,int>>p;
	while(true){
		int tp=top[u];
		p.emplace_back(tin[tp],tin[u]+1);
		if(tp==0)break;
		u=par[tp];
	}
	reverse(p.begin(),p.end());
	for(auto q:p)gt1(q.first,q.second);
}
struct it{
	int t[2*N];
	int get(int l,int r){
		l+=N;
		r+=N;
		int ans=0;
		while(l<r){
			 if(l&1)ans+=t[l++];
			 if(r&1)ans+=t[--r];
			 l/=2,r/=2;
		}
		return ans;
	}
	void inc(int x,int y){
		x+=N;
		t[x]+=y;
		while(x>1)t[x>>1]=t[x]+t[x^1],x>>=1;
	}
} myit;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	n=100000;
	cin>>n;
	for(int i=0;i<n;++i){
		C[i]=i;
		cin>>C[i];
	}
	vector<pair<int,int>>p;
	for(int i=0;i<n-1;++i){
		 int a=rand()%(i+1),b=i+1;
		 cin>>a>>b;
		 --a,--b;
		 p.emplace_back(a,b);
		 g[a].push_back(b);
		 g[b].push_back(a);
	}
	vector<int>cs(C,C+n);
	sort(cs.begin(),cs.end());
	for(int i=0;i<n;++i)
		C[i]=lower_bound(cs.begin(),cs.end(),C[i])-cs.begin()+1;
	d1(0);
	d2(0);
	st(0,C[0]);
	int s=0;
	for(auto q:p){
		int a,b;
		tie(a,b)=q;
		gt(a);
		auto&lol=glob;
		s+=lol.size();
		assert(s<=2000000);
		nagai ans=0;
		for(int i=0;i<lol.size();++i){
			ans+=(nagai)lol[i].first*myit.get(lol[i].second+1,N);
			myit.inc(lol[i].second,lol[i].first);
		}
		for(int i=0;i<lol.size();++i)
			myit.inc(lol[i].second,-lol[i].first);
		cout<<ans<<'\n';
		st(b,C[b]);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<lol.size();++i){
               ~^~~~~~~~~~~
construction.cpp:181:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<lol.size();++i)
               ~^~~~~~~~~~~

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