제출 #1138104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138104		NK_	별자리 3 (JOI20_constellation3)	C++20	100 / 100	340 ms	71688 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<V<AR<int, 3>>> in;

	set<AR<int, 3>> S;

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

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

		while(sz(S) && (*begin(S))[0] <= h) {
			in.back().pb(*begin(S));
			S.erase(begin(S));
		}
	};	

	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.insert({h, i, idx});
		}
	}

	function<ll(int, int, int)> dnc = [&](int l, int r, int i) {
		// cout << l << " " << r << " " << i << endl;
		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();
			// cout << "===> " << lx << " " << rx << " " << ix << endl;
			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];
			// cout << "ADDED: " << l << " " << lx << " - " << rx << " " << r << endl;
			B.add(l + 1, lx, res[i]); B.add(rx, r - 1, res[i]);
		}

		// cout << l << " " << r << " -> " << i << endl;
		// cout << "ANS: " << bst << endl;
		for(auto& [h, pos, idx] : in[i]) {
			// cout << "STAR: " << pos << " " << h;
			// cout << " -> " << B.get(pos) << " " << C[idx] << endl;
			ll ans = B.get(pos) + C[idx];
			bst = max(bst, ans);
		}

		// cout << l << " " << r << "  << i << " ----> " << bst << endl;

		return bst;
	};

	nxt[0].pop_back();

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

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