Submission #763977

#	Time	Username	Problem	Language	Result	Execution time	Memory
763977		minhcool	Construction of Highway (JOI18_construction)	C++17	100 / 100	500 ms	50316 KiB

construction

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, c[N];

vector<int> Adj[N];

bool ck[N];
int ind[N];

int sz[N];

void dfs(int u){
//	cout << u << "\n";
	sz[u] = 1;
	for(auto v : Adj[u]){
		dfs(v);
		sz[u] += sz[v];
	}
}

int cnt;
int num[N], pos[N], len[N], head[N], par[N];

void hld(int u, int nw){
	//cout << u << " " << nw << "\n";
	if(nw){
		cnt++;
		num[u] = cnt; pos[u] = 1;
		head[cnt] = u;
	}
	ii mx = {-1, -1};
	for(auto v : Adj[u]) mx = max(mx, {sz[v], v});
	if(mx.fi < 0) return;
	num[mx.se] = num[u]; pos[mx.se] = pos[u] + 1;
	hld(mx.se, 0);
	for(auto v : Adj[u]) if(v != mx.se) hld(v, 1);
}

set<ii> segs[N];// start_pos & c[i]

int bit[N], posi[N];

vector<int> used;

void upd(int id, int val){
	used.pb(id);
	for(; id <= n; id += id & -id){
		bit[id] += val;
	//	cout << id << " " << n << " " << "OK\n";
	}
}

int get(int id){
	int ans = 0;
	for(; id; id -= id & -id) ans += bit[id];
	return ans;
}

int answer = 0;

void upd(int id){
	int savee = posi[id];
	while(id){
		set<ii>::iterator it = segs[num[id]].upper_bound({pos[id], oo});
	//	int tempo = (it == segs[num[id]].end() ? len[num[id]] : (*it).fi - 1);
		it--;
	//	id = par[head[num[id]]];
		//cout << id << "\n";
	//	continue;
		int lst = (*it).se, lstt = pos[id] + 1;
		vector<ii> v;
		for(; ; it--){
			v.pb((*it));
			//assert((*it).se != 0);
		//	cout << "HEHEHE " << (*it).se << "\n";
	//		cout << lstt << " " << (*it).fi << "\n";
	//		cout << (*it).fi << " " << (*it).se << " " << (lstt - (*it).fi) << " " << get((*it).se - 1) << "\n";
			answer += (lstt - (*it).fi) * get((*it).se - 1);
			upd((*it).se, (lstt - (*it).fi));
			if(it == segs[num[id]].begin()) break;
			lstt = (*it).fi;
		}
	//	id = par[head[num[id]]];
	//	continue;
		for(auto it : v) segs[num[id]].erase(it);
		segs[num[id]].insert({1, savee});
		it = segs[num[id]].lower_bound({pos[id] + 1, -oo});
		if(it == segs[num[id]].end() || (*it).fi != (pos[id] + 1)) segs[num[id]].insert({pos[id] + 1, lst});
		id = par[head[num[id]]];
	}
} 

#ifdef local
void process(){
	cin >> n;
	vector<int> diff;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
		diff.pb(c[i]);
	}
	diff.pb(-1);
	sort(diff.begin(), diff.end());
	diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
	for(int i = 1; i <= n; i++) posi[i] = lower_bound(diff.begin(), diff.end(), c[i]) - diff.begin(); 
	ck[1] = 1;	
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		if(!ck[x]){
			//cout << x << "\n";
			Adj[y].pb(x);
			par[x] = y;
			ck[x] = 1;
			ind[i] = x;
		}
		else{
			Adj[x].pb(y);
			par[y] = x;
			ck[y] = 1;
			ind[i] = y;
		}
	}
	dfs(1);
	hld(1, 1);
	for(int i = 1; i <= n; i++){
		len[num[i]] = max(len[num[i]], pos[i]);
		segs[i].insert({1, n});
	}
	//return;
	for(int i = 1; i < n; i++){
		answer = 0;
		upd(ind[i]);
		cout << answer << "\n";
		for(auto it : used){
			int temp = it;
			for(; temp <= n; temp += temp & -temp) bit[temp] = 0;
		}
		used.clear();
	}
}

signed main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	process();
}
#endif

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