Submission #716470

#	Time	Username	Problem	Language	Result	Execution time	Memory
716470		pavement	Construction of Highway (JOI18_construction)	C++17	100 / 100	839 ms	37184 KiB

construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, idx, u[100005], v[100005], C[100005], par[100005], sz[100005], hv[100005], pos[100005], rev[100005], ft[100005];
vector<int> disc, adj[100005];
vector<iii> segs;
stack<int> rb;

int ls(int x) {
	return x & -x;
}

void reset() {
	while (!rb.empty()) {
		int x = rb.top();
		ft[x] = 0;
		rb.pop();
	}
}

void upd(int p, int v) {
	for (; p <= N; p += ls(p)) {
		rb.push(p);
		ft[p] += v;
	}
}

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

struct node {
	node *left, *right;
	int S, E, mxval, mival, pv;
	bool ip;
	node(int _s, int _e) : S(_s), E(_e), ip(0) {
		if (S == E) {
			mxval = mival = C[rev[S]];
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		mxval = max(left->mxval, right->mxval);
		mival = min(left->mival, right->mival);
	}
	void prop() {
		if (S == E || !ip) return;
		left->mxval = left->mival = left->pv = right->mxval = right->mival = right->pv = pv;
		left->ip = right->ip = 1;
		ip = 0;
	}
	void get_seg(int l, int r) {
		if (l > E || r < S) return;
		if (l <= S && E <= r && mxval == mival) {
			segs.eb(S, E, mxval);
			return;
		}
		prop();
		left->get_seg(l, r);
		right->get_seg(l, r);
	}
	void set(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			mxval = mival = pv = v;
			ip = 1;
			return;
		}
		prop();
		left->set(l, r, v);
		right->set(l, r, v);
		mxval = max(left->mxval, right->mxval);
		mival = min(left->mival, right->mival);
	}
} *root;

int get_sz(int n) {
	sz[n] = 1;
	for (auto u : adj[n]) {
		sz[n] += get_sz(u);
	}
	return sz[n];
}

void dfs(int n) {
	pos[n] = ++idx;
	rev[pos[n]] = n;
	int cur_mx = -1;
	for (int i = 0; i < (int)adj[n].size(); i++) {
		if (sz[adj[n][i]] > cur_mx) {
			cur_mx = sz[adj[n][i]];
			swap(adj[n][0], adj[n][i]);
		}
	}
	for (int i = 0; i < (int)adj[n].size(); i++) {
		if (i == 0) {
			hv[adj[n][i]] = hv[n];
		} else {
			hv[adj[n][i]] = adj[n][i];
		}
		dfs(adj[n][i]);
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
		disc.pb(C[i]);
	}
	sort(disc.begin(), disc.end());
	for (int i = 1; i <= N; i++) {
		C[i] = lower_bound(disc.begin(), disc.end(), C[i]) - disc.begin() + 1;
	}
	for (int i = 1; i < N; i++) {
		cin >> u[i] >> v[i];
		par[v[i]] = u[i];
		adj[u[i]].pb(v[i]);
	}
	get_sz(1);
	hv[1] = 1;
	dfs(1);
	root = new node(1, N);
	for (int i = 1; i < N; i++) {
		segs.clear();
		for (int x = u[i]; x; x = par[hv[x]]) {
			root->get_seg(pos[hv[x]], pos[x]);
			root->set(pos[hv[x]], pos[x], C[v[i]]);
		}
		int cur = 0;
		sort(segs.begin(), segs.end());
		reset();
		for (auto [l, r, val] : segs) {
			cur += qry(N - val) * (r - l + 1);
			upd(N - val + 1, r - l + 1);
		}
		cout << cur << '\n';
	}
}

Compilation message (stderr)

construction.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main() {
      | ^~~~

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