제출 #1154513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154513		beaboss	별자리 3 (JOI20_constellation3)	C++20	0 / 100	2 ms	5184 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(map<ll, ll> &m, pii x) {
	auto it = m.upper_bound(x.f);
	if (it != m.begin()) {
		auto bef = prev(it, 1);
		if ((*bef).s >= x.s) return;
	}

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

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


}

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

	ll cur = rmq(l, r).s;
	// cout << l << r << cur << endl;
	auto le = solve(l, cur-1);
	auto ri = solve(cur+1, r);

	ll bestl = 0;


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

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

	// cout << cur << bestl << bestr << endl;

	map<ll, ll> res;

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

	// cout << "------" << cur << endl;

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


	for (auto x: le) ins(res, {x.f, x.s + bestr});
	for (auto x: ri) ins(res, {x.f, x.s + bestl});

	// cout << cur << endl;
	// for (auto x: res) cout<< x.f << x.s << endl;
	// 	cout << endl;
	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[i + (1 << (j-1))][j-1]);
		}
	}
	// cout << rmq(1, 5).s << endl;

	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) {
		best = max(best, x.s);
	}

	cout << sm-best << endl;


}

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