Submission #212288

#	Time	Username	Problem	Language	Result	Execution time	Memory
212288		ksun48	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	324 ms	82552 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

using ll = long long;

template<class T>
struct RMQ {
	vector<vector<T>> jmp;

	RMQ(const vector<T>& V) {
		int N = sz(V), on = 1, depth = 1;
		while (on < sz(V)) on *= 2, depth++;
		jmp.assign(depth, V);
		rep(i,0,depth-1) rep(j,0,N)
			jmp[i+1][j] = max(jmp[i][j],
			jmp[i][min(N - 1, j + (1 << i))]);
	}

	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return max(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

RMQ<pair<int,int> > rmq({});

vector<pair<int,int> > a;
vector<ll> base_cost;
vector<multiset<pair<int, ll> > > cost;
vector<ll> no_star_cost;

int merge(int x, int y){
	if(cost[x].size() < cost[y].size()) swap(x, y);
	for(pair<int, ll> p : cost[y]){
		cost[x].insert({p.first, p.second + no_star_cost[x] - no_star_cost[y]});
	}
	base_cost[x] += no_star_cost[y] + base_cost[y];
	return x;
}

int solve(int l, int r, int cap){
	int cur;
	if(l + 1 == r){
		cur = l;
	} else {
		pair<int,int> v = rmq.query(l, r);
		int best = v.second;
		int val = v.first;
		cur = solve(best, best + 1, val);
		if(l < best){
			cur = merge(cur, solve(l, best, val));
		}
		if(best + 1 < r){
			cur = merge(cur, solve(best + 1, r, val));
		}
	}
	while(!cost[cur].empty() && (*cost[cur].begin()).first <= cap){
		no_star_cost[cur] = max(no_star_cost[cur], (*cost[cur].begin()).second);
		cost[cur].erase(cost[cur].begin());
	}
	return cur;
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	a.resize(n);

	base_cost.resize(n);
	no_star_cost.resize(n);
	cost.resize(n);
	for(int i = 0; i < n; i++){
		cin >> a[i].first;
		a[i].second = i;
	}
	rmq = RMQ<pair<int,int> >(a);
	int m;
	cin >> m;
	ll tot_cost = 0;
	for(int i = 0; i < m; i++){
		ll x, y, c;
		cin >> x >> y >> c;
		x--;
		cost[x].insert({y, c});
		tot_cost += c;
	}
	int z = solve(0, n, n+1);
	cout << tot_cost - (no_star_cost[z] + base_cost[z]) << '\n';
}

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