Submission #1154524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154524		beaboss	별자리 3 (JOI20_constellation3)	C++20	100 / 100	302 ms	136636 KiB

constellation3

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll N = 2e5 + 10;
const ll B = 20;
ll a[N];
pii sp[N][B];
vpii by_row[N];

pii rmq(ll l, ll r) {
	r++; // exclusive
	ll d = floor(log2(r - l));
	return max(sp[l][d], sp[r-(1 << d)][d]);
}

void ins(pair<map<ll, ll>, ll> &obj, pii x) {
	map<ll, ll>& m = obj.f;
	auto it = m.upper_bound(x.f);
	if (it != m.begin()) {
		auto bef = prev(it, 1);
		if ((*bef).s + obj.s >= x.s) return;
	}

	while (it != m.end() && (*it).s + obj.s <= x.s) {

		it=next(it, 1);
		m.erase(prev(it, 1));
	}
	m[x.f]=x.s - obj.s;


}

pair<map<ll, ll>, ll> solve(ll l, ll r) {
	if (l > r) return {};
	if (r == l) {
		pair<map<ll, ll>, ll> res;
		for (auto x: by_row[l]) ins(res, x);
		return res;
	}

	ll cur = rmq(l, r).s;

	auto le = solve(l, cur-1);
	auto ri = solve(cur+1, r);

	ll bestl = 0;


	auto it = le.f.begin();
	while (it != le.f.end() && (*it).f <= a[cur]) {
		bestl=max(bestl, (*it).s + le.s);
		it = next(it, 1);
		le.f.erase(prev(it, 1));
	}

	it = ri.f.begin();
	ll bestr = 0;
	while (it != ri.f.end() && (*it).f <= a[cur]) {
		bestr=max(bestr, (*it).s + ri.s);
		it = next(it, 1);
		ri.f.erase(prev(it, 1));
	}


	pair<map<ll, ll>, ll> res;

	res.f[a[cur]]=bestr + bestl;

	for (auto x: by_row[cur]) ins(res, {x.f, x.s + bestr + bestl});

	ri.s += bestl;
	le.s += bestr;

	if (res.f.size() < le.f.size()) swap(res, le);
	for (auto x: le.f) ins(res, {x.f, x.s + le.s});

	if (res.f.size() < ri.f.size()) swap(res, ri);
	for (auto x: ri.f) ins(res, {x.f, x.s + ri.s});

	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n;
	cin >> n;

	FOR(i, 1, n+1) {
		cin >> a[i];
		sp[i][0]={a[i], i};
	}
	

	FOR(j, 1, B) {
		FOR(i, 1, n+1) {
			sp[i][j] = max(sp[i][j-1], sp[min(i + (1 << (j-1)), N-1)][j-1]);
		}
	}
	


	ll s;
	cin >> s;
	ll sm = 0;
	FOR(_, 0, s) {
		ll x, y, c;
		cin >> x >> y >> c;
		sm += c;
		by_row[x].pb({y, c});
	}
	

	auto res = solve(1, n);
	ll best = 0;
	for (auto x: res.f) {
		best = max(best, x.s + res.s);
	}

	cout << sm-best << endl;


}

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