Submission #1138134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138134		NK_	Constellation 3 (JOI20_constellation3)	C++20	0 / 100	1 ms	576 KiB

constellation3

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define f first
#define s second

using ll = long long;

template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using vl = V<ll>;

const int INF = 1e9 + 10;

struct BIT {
	vl data; int N; void init(int n) { N = n; data = vl(N); }
	void add(int p, ll x) { for(++p;p<=N;p+=p&-p) data[p - 1] += x; }
	void add(int l, int r, ll x) { add(l, +x); add(r + 1, -x); }
	ll get(int r) { ll s = 0; for(++r;r;r-=r&-r) s += data[r - 1]; return s; }
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	vi A(N + 2, INF); for(int i = 1; i <= N; i++) cin >> A[i];

	BIT B; B.init(N + 2);

	// stack solves all problems
	// including cancer (impl)

	int M; cin >> M;	

	vl C(M);
	V<vpi> E(N + 2); ll all = 0;
	for(int _ = 0; _ < M; _++) {
		int i, h; cin >> i >> h >> C[_];
		all += C[_];
		E[i].pb(mp(h, _));
	}

	V<vpi> nxt(N + 2); int cur = 0;
	V<vpi> in;

	V<vpi> S(N + 1);

	auto add = [&](int lx, int rx) {
		nxt[lx].pb(mp(rx, cur));  
		++cur; in.pb({});

		int H = min(A[lx], A[rx]);

		for(int h = 1; h <= H; h++) {
			for(auto& x : S[h]) in.back().pb(x);
			S[h] = {};
		}
	};	

	vi stk = {0};
	for(int i = 1; i <= N + 1; i++) {
		while(stk.back() != 0 && A[stk.back()] <= A[i]) {
			add(stk.back(), i); stk.pop_back();
		}	

		add(stk.back(), i); stk.pb(i);

		for(auto& [h, idx] : E[i]) {
			S[h].pb(mp(i, idx));
		}
	}

	function<ll(int, int, int)> dnc = [&](int l, int r, int i) {
		if (r - l <= 1) return 0LL;

		int lx = l, rx = -1, ix = -1;

		vpi div; vl res;
		do {
			tie(rx, ix) = nxt[lx].back(); nxt[lx].pop_back();
			res.pb(dnc(lx, rx, ix));
			div.pb(mp(lx, rx));
			lx = rx;
		} while(rx != r);

		int m = sz(res);
		ll bst = accumulate(begin(res), end(res), 0LL);

		for(int i = 0; i < m; i++) {
			auto [lx, rx] = div[i];
			B.add(l + 1, lx, res[i]); B.add(rx, r - 1, res[i]);
		}

		for(auto& [pos, idx] : in[i]) {
			ll ans = B.get(pos) + C[idx];
			bst = max(bst, ans);
		}
		return bst;
	};

	nxt[0].pop_back();

	cout << all - dnc(0, N + 1, cur - 1) << nl;
	
	exit(0-0);
}

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