Submission #529075

#	Time	Username	Problem	Language	Result	Execution time	Memory
529075		fhvirus	Construction of Highway (JOI18_construction)	C++17	16 / 100	2070 ms	8336 KiB

construction

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

struct LISAN : vector<int> {
	void done() { sort(AI()); erase(unique(AI()), end()); }
	int operator () (const int& v) const { return lower_bound(AI(), v) - begin(); }
};
struct BIT {
	int n; vector<int> val;
	BIT(int _n = 0): n(_n), val(n + 1, 0) {}
	void modify(int p, int v) {
		for (; p <= n; p += p & -p)
			val[p] += v;
	}
	int query(int p) {
		int r = 0;
		for (; p > 0; p -= p & -p)
			r += val[p];
		return r;
	}
} bit;

const int kN = 100'001;
int N, C[kN], A[kN], B[kN];
int par[kN];
vector<int> chi[kN];

int get_inversion(vector<int>& val) {
	int ans = 0;
	for (int &i: val) {
		ans += bit.query(i - 1);
		bit.modify(i, 1);
	}
	for (int &i: val)
		bit.modify(i, -1);
	return ans;
}

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

	cin >> N;
	LISAN lisan;
	for (int i = 1; i <= N; ++i) {
		cin >> C[i];
		lisan.pb(C[i]);
	}
	lisan.done();
	for (int i = 1; i <= N; ++i)
		C[i] = lisan(C[i]) + 1;
	bit = BIT(lisan.size());
	for (int i = 1; i < N; ++i) {
		cin >> A[i] >> B[i];
		par[B[i]] = A[i];
		chi[A[i]].pb(B[i]);
	}

	for (int i = 1; i < N; ++i) {
		int u = A[i];
		vector<int> val;
		do {
			val.pb(C[u]);
			u = par[u];
		} while (u != 0);

		cout << get_inversion(val) << '\n';

		// set value for 1 -> B[j];
		u = A[i];
		do {
			C[u] = C[B[i]];
			u = par[u];
		} while (u != 0);
	}
	
	return 0;
}

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