Submission #733059

#	Time	Username	Problem	Language	Result	Execution time	Memory
733059		SanguineChameleon	Fireworks (APIO16_fireworks)	C++17	100 / 100	208 ms	73356 KiB

fireworks

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct func {
	long long slope = 0;
	long long last = 0;
	priority_queue<long long> q;

	void init(int w) {
		slope = 1;
		last = 0;
		q.push(w);
		q.push(w);
	}

	long long update(int w) {
		long long lt = -1;
		long long rt = -1;
		while (slope > 0) {
			long long cur = q.top();
			q.pop();
			long long prv = q.top();
			if (slope == 1) {
				lt = prv;
				rt = cur;
			}
			slope--;
			last -= slope * (cur - prv);
		}
		q.pop();
		q.push(lt + w);
		q.push(rt + w);
		slope = 1;
		return last;
	}
	
	void merge(func &f2) {
		if (q.empty()) {
			slope = f2.slope;
			last = f2.last;
			swap(q, f2.q);
			return;
		}
		if (q.top() > f2.q.top()) {
			last = last + (f2.last + f2.slope * (q.top() - f2.q.top()));
		}
		else {
			last = f2.last + (last + slope * (f2.q.top() - q.top()));
		}
		slope += f2.slope;
		if (q.size() < f2.q.size()) {
			swap(q, f2.q);
		}
		while (!f2.q.empty()) {
			q.push(f2.q.top());
			f2.q.pop();
		}
	}
};

const int maxN = 3e5 + 20;
vector<pair<int, int>> ch[maxN];
func f[maxN];
int N, M;

void dfs(int u) {
	for (auto p: ch[u]) {
		int v = p.first;
		int w = p.second;
		if (N + 1 <= v && v <= N + M) {
			f[v].init(w);
		}
		else {
			dfs(v);
			f[v].update(w);
		}
		f[u].merge(f[v]);
	}
}

void just_do_it() {
	cin >> N >> M;
	for (int v = 2; v <= N + M; v++) {
		int u, w;
		cin >> u >> w;
		ch[u].emplace_back(v, w);
	}
	dfs(1);
	cout << f[1].update(0);
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45