Submission #470542

#	Time	Username	Problem	Language	Result	Execution time	Memory
470542		Namnamseo	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	1025 ms	58228 KiB

constellation3

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll=long long;
using pp=pair<int,int>;
const int maxn = int(2e5) + 10;

int n;
int a[maxn];

vector<pair<pp,int>> gnum;

namespace {
	int tx[18][maxn];

	void build() {
		for (int i=1; i<=n; ++i) tx[0][i] = i;
		for (int i=1; i<=17; ++i) for (int j=1; j<=n; ++j) {
			tx[i][j] = tx[i-1][j];
			if (j+(1<<(i-1)) <= n) {
				int ia = tx[i][j], ib = tx[i-1][j+(1<<(i-1))];
				if (a[ia] < a[ib]) tx[i][j] = ib;
			}
		}
	}

	int maxi(int l, int r) {
		int i = (31-__builtin_clz(r-l+1));
		int ia = tx[i][l], ib = tx[i][r-(1<<i)+1];
		return (a[ia]>a[ib]) ? ia : ib;
	}

	int wrap_v(int x, int y) {
		int l = x, r = x;
		for (int i=17; 0<=i; --i) {
			int tl = l - (1<<i);
			if (1 <= tl && a[tx[i][tl]] < y) l = tl;
			int tr = r + (1<<i);
			if (tr <= n && a[tx[i][r+1]] < y) r = tr;
		}
		return lower_bound(gnum.begin(), gnum.end(),
			pair<pp, int>{{l, r}, -1})->second;
	}
}

vector<int> te[maxn];
int root;
vector<pp> paths[maxn];
int gdfs(int l, int r) {
	static int gn;
	int me = ++gn; gnum.push_back({{l, r}, me});
	if (l == r) return me;
	int i = maxi(l, r);
	if (l < i) te[me].push_back(gdfs(l, i-1));
	if (i < r) te[me].push_back(gdfs(i+1, r));
	return me;
}

int tin[maxn], tout[maxn], nt;
void tdfs1(int x) {
	tin[x] = ++nt; for (int y : te[x]) tdfs1(y); tout[x] = nt;
}

ll dp[maxn];
struct It {
	const static int M = 262144;
	ll t[M<<1];
	void upd(int l, int r, ll v) {
		for (l+=M, r+=M; l<=r; l/=2, r/=2) {
			if (l%2==1) t[l++] += v;
			if (r%2==0) t[r--] += v;
		}
	}
	ll get(int p) { ll ret = 0;
		for (p+=M; p; p/=2) ret += t[p];
		return ret;
	}
} giveup;

void tdfs2(int x) {
	ll cds = 0;
	for (int y:te[x]) tdfs2(y), cds += dp[y];
	ll mdf = 0;
	for (auto &tmp:paths[x]) {
		int to, c; tie(to, c) = tmp;
		mdf = max(mdf, c + giveup.get(tin[to]));
	}
	dp[x] = cds + mdf;
	giveup.upd(tin[x], tout[x], -mdf);
}

int main() { cin.tie(0)->sync_with_stdio(0);
	cin >> n; for (int i=1; i<=n; ++i) cin >> a[i];
	build();

	ll csum = 0;
	root = gdfs(1, n);
	sort(gnum.begin(), gnum.end());
	{ int m; cin >> m;
	for (;m--;) {
		int x, y, c; cin >> x >> y >> c; csum += c;
		int up = wrap_v(x, y), down = wrap_v(x, a[x]+1);
		paths[up].push_back({down, c});
	} }

	tdfs1(root);
	tdfs2(root);

	ll ans = csum - dp[root];
	cout << ans << '\n';

	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65