제출 #470536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470536		Namnamseo	별자리 3 (JOI20_constellation3)	C++17	100 / 100	1278 ms	90132 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];

map<pp,int> gnum; int gn;

struct Sparse {
	pp tx[20][maxn];

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

	int maxi(int l, int r) {
		int w = r-l+1;
		for (int i=0;;++i) if (2*(1<<i) >= w) {
			return max(tx[i][l], tx[i][r-(1<<i)+1]).second;
		}
	}

	int wrap_v(int x, int y) {
		int l = x, r = x;
		for (int i=19; 0<=i; --i) {
			int tl = l - (1<<i);
			if (1 <= tl && tx[i][tl].first < y) l = tl;
			int tr = r + (1<<i);
			if (tr <= n && tx[i][r+1].first < y) r = tr;
		}
		return gnum[{l, r}];
	}
} tree;

vector<int> te[maxn];
int root;
vector<pp> paths[maxn];
int gdfs(int l, int r) {
	int me = ++gn; gnum[{l, r}] = me;
	if (l == r) return me;
	int i = tree.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];
	tree.build();

	ll csum = 0;
	root = gdfs(1, n);
	{ int m; cin >> m;
	for (;m--;) {
		int x, y, c; cin >> x >> y >> c; csum += c;
		int up = tree.wrap_v(x, y), down = tree.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