Submission #211177

#	Time	Username	Problem	Language	Result	Execution time	Memory
211177		nvmdava	Construction of Highway (JOI18_construction)	C++17	100 / 100	933 ms	27640 KiB

construction

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f

vector<int> ch[N];

int le[N], c[N], ri[N], p[N][17], d[N];
int cntr = 0;
int bit[N], seg[N * 3];

void updateseg(int id, int l, int r, int x, int v){
	if(l > x || r < x) return;
	seg[id] = max(seg[id], v);
	if(l == r) return;
	int m = (l + r) >> 1;
	updateseg(id << 1, l, m, x, v);
	updateseg(id << 1 | 1, m + 1, r, x, v);
}

int queryseg(int id, int l, int r, int L, int R){
	if(L <= l && r <= R) return seg[id];
	if(l > R || r < L) return 0;
	int m = (l + r) >> 1;
	return max(queryseg(id << 1, l, m, L, R), queryseg(id << 1 | 1, m + 1, r, L, R));
}

void updatebit(int x, int v){
	while(x < N){
		bit[x] += v;
		x += x & -x;
	}
}
int querybit(int x){
	int s = 0;
	while(x){
		s += bit[x];
		x -= x & -x;
	}
	return s;
}

void dfs(int v = 1){
	le[v] = ++cntr;
	for(int i = 0; i < 16; ++i)
		p[v][i + 1] = p[p[v][i]][i];

	for(int x : ch[v]){
		p[x][0] = v;
		d[x] = d[v] + 1;
		dfs(x);
	}
	ri[v] = cntr;
}

map<int, int> cmp;

vector<pair<int, int > > mark;

int ord[N];

int lca(int v, int u){
	for(int i = 16; i >= 0; --i)
		if(le[p[v][i]] > le[u] || ri[u] > ri[p[v][i]])
			v = p[v][i];
	return v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i){
    	cin>>c[i];
    	cmp[c[i]] = 0;
    }
    ri[0] = n;

    for(auto& x : cmp)
	    x.ss = ++cntr;
    for(int i = 1; i <= n; ++i)
    	c[i] = n + 1 - cmp[c[i]];

    for(int i = 2; i <= n; ++i){
    	int v;
    	cin>>v>>ord[i];
    	ch[v].push_back(ord[i]);
    }
    cntr = 0;
    updateseg(1, 1, n, 1, 1);
    ord[1] = 1;
    dfs();
    for(int i = 2; i <= n; ++i){
    	int v = 1;
    	ll ans = 0;
    	while(v != ord[i]){
    		int u = ord[queryseg(1, 1, n, le[v], ri[v])];
    		int val = c[u];
    		u = lca(ord[i], u);
    		ans += 1LL * querybit(val - 1) * (d[u] - d[v]);
    		updatebit(val, d[u] - d[v]);
    		mark.push_back({val, d[u] - d[v]});
    		v = u;
    	}
    	updateseg(1, 1, n, le[ord[i]], i);
    	while(!mark.empty()){
    		updatebit(mark.back().ff, -mark.back().ss);
    		mark.pop_back();
    	}
    	cout<<ans<<'\n';
    }
}

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