Submission #1153070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153070		AmirAli_H1	Construction of Highway (JOI18_construction)	C++20	100 / 100	296 ms	22980 KiB

construction

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 17) + 4;

int n; int A[maxn];
vector<int> adj[maxn], arr;
vector<int> Q; int h[maxn], sz[maxn];
int st[maxn], ft[maxn], timer, ind[maxn];
int hld[maxn], par[maxn]; vector<pii> ls, lsx;
ll tx[maxn]; pii t[2 * maxn];

void addx(int i, ll x) {
	for (++i; i < maxn; i += (i & -i)) tx[i] += x;
}

ll getx(int i) {
	ll res = 0;
	for (++i; i > 0; i -= (i & -i)) res += tx[i];
	return res;
}

pii f(pii a, pii b) {
	pii res; res.F = -1;
	if (a.S == -1 || b.S == -1 || a.S != b.S) res.S = -1;
	else res.S = a.S;
	return res;
}

void shift(int v, int tl, int tr) {
	int x = t[v].F; t[v].F = -1;
	if (x == -1 || tr - tl == 1) return ;
	t[2 * v + 1].F = t[2 * v + 1].S = x;
	t[2 * v + 2].F = t[2 * v + 2].S = x;
}

void build(int v, int tl, int tr) {
	t[v].F = -1;
	if (tr - tl == 1) {
		t[v].S = A[ind[tl]];
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void set_val(int v, int tl, int tr, int l, int r, int x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	shift(v, tl, tr);
	if (l == tl && r == tr && t[v].S != -1) {
		if (len(lsx) == 0 || lsx.back().F != t[v].S) {
			lsx.pb(Mp(t[v].S, tr - tl));
		}
		else {
			lsx[len(lsx) - 1].S += (tr - tl);
		}
		t[v].F = t[v].S = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_val(2 * v + 1, tl, mid, l, r, x);
	set_val(2 * v + 2, mid, tr, l, r, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void pre_dfs(int v, int p = -1) {
	sz[v] = 1;
	for (int u : adj[v]) {
		h[u] = h[v] + 1;
		pre_dfs(u, v);
		sz[v] += sz[u];
	}
}

bool cmp(int i, int j) {
	return (sz[i] > sz[j]);
}

void res_dfs(int v, int p = -1) {
	st[v] = timer++; ind[st[v]] = v;

	par[v] = p;
	if (p != -1 && st[p] + 1 == st[v]) hld[v] = hld[p];
	else hld[v] = v;

	sort(all(adj[v]), cmp);
	for (int u : adj[v]) {
		res_dfs(u, v);
	}
	ft[v] = timer;
}

ll setx(int v, int x) {
	ls.clear(); lsx.clear();
	while (v != -1) {
		ls.pb(Mp(st[hld[v]], st[v] + 1));
		v = par[hld[v]];
	}
	reverse(all(ls));
	for (auto f : ls) {
		int l = f.F, r = f.S;
		set_val(0, 0, n, l, r, x);
	}
	ll res = 0;
	for (int i = len(lsx) - 1; i >= 0; i--) {
		int x = lsx[i].F, cnt = lsx[i].S;
		res += 1ll * cnt * getx(x - 1); addx(x, cnt);
	}
	for (int i = len(lsx) - 1; i >= 0; i--) {
		int x = lsx[i].F, cnt = lsx[i].S;
		addx(x, -cnt);
	}
	return res;
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i]; arr.pb(A[i]);
	}
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	for (int i = 0; i < n; i++) {
		A[i] = lower_bound(all(arr), A[i]) - arr.begin();
	}
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		adj[u].pb(v); Q.pb(v);
	}
	pre_dfs(0); res_dfs(0);

	build(0, 0, n);
	for (int i = 0; i < n - 1; i++) {
		int v = Q[i];
		cout << setx(par[v], A[v]) << endl;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	return 0;
}

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