Submission #513186

#	Time	Username	Problem	Language	Result	Execution time	Memory
513186		8e7	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	571 ms	58664 KiB

constellation3

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define int long long
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], lef[maxn], rig[maxn], anc[18][maxn], lc[maxn], rc[maxn];
vector<pii> que[maxn];
ll dp[maxn];
struct BIT{
	ll bit[maxn];
	void modify(int ind, ll val) {
		if (ind <= 0) return;
		for (;ind < maxn;ind += ind & (-ind))bit[ind] += val; 
	}
	ll query(int ind) {
		ll ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
	void rmod(int l, int r, ll val) { //[l, r]
		//debug("mod", l, r, val);
		modify(r+1, -val);modify(l, val);
	}
} b;
void dfs(int n, int par) {
	if (lc[n]) dfs(lc[n], n);	
	if (rc[n]) dfs(rc[n], n);
	if (lc[n]) b.rmod(n, rig[n]-1, dp[lc[n]]);
	if (rc[n]) b.rmod(lef[n]+1, n, dp[rc[n]]);
	dp[n] = b.query(n);
	for (auto p:que[n]) {
		//debug(n, p.ff, p.ss);
		dp[n] = max(dp[n], p.ss + b.query(p.ff));
	}
	//debug(n, lc[n], rc[n]);
}
signed main() {
	io
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	stack<int> stk;
	for (int i = 1;i <= n;i++) {
		while (stk.size() && a[i] >= a[stk.top()]) {
			rig[stk.top()] = i;
			stk.pop();
		}
		lef[i] = (stk.size() ? stk.top() : 0);
		stk.push(i);
	}
	while (stk.size()) {
		rig[stk.top()] = n+1;
		stk.pop();
	}
	int root = 0;
	for (int i = 1;i <= n;i++) {
		int le = 0, ri = 0;
		if (lef[i] != 0) le = a[lef[i]];
		if (rig[i] != n+1) ri = a[rig[i]];
		if (!le && !ri) root = i, anc[0][i] = i;
		else if (!le) anc[0][i] = rig[i];
		else if (!ri) anc[0][i] = lef[i];
		else {
			if (le <= ri) anc[0][i] = lef[i];
			else anc[0][i] = rig[i];
		}
		//debug(i, anc[0][i]);
		if (i != root) {
			if (anc[0][i] < i) rc[anc[0][i]] = i;
			else lc[anc[0][i]] = i;
		}
	}
	for (int i = 1;i < 18;i++) {
		for (int j = 1;j <= n;j++) anc[i][j] = anc[i-1][anc[i-1][j]];
	}
	int m;
	cin >> m;
	ll tot = 0;
	for (int i = 0;i < m;i++) {
		int x, y, c;
		cin >> x >> y >> c;
		tot += c;
		int to = x;
		for (int j = 17;j >= 0;j--) {
			if (a[anc[j][to]] < y) to = anc[j][to];
		}
		que[to].push_back({x, c});
		//debug(x, y, c, to);
	}
	dfs(root, 0);
	cout << tot - dp[root] << "\n";	
}

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