Submission #563132

#	Time	Username	Problem	Language	Result	Execution time	Memory
563132		hollwo_pelw	Fireworks (APIO16_fireworks)	C++17	100 / 100	186 ms	46156 KiB

fireworks

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	cout << "\nExecution time : " << duration_cast<milliseconds> (steady_clock::now() - start).count() << "[ms]" << endl;
#endif
}

#define int long long

const int N = 3e5 + 5;
// wtf slope trick

int n, m, p[N], c[N];

struct slope_t {
	priority_queue<int> pq;
	int slp = 0, res = 0;

	inline void swap(slope_t &oth) {
		pq.swap(oth.pq);
		std::swap(slp, oth.slp);
		std::swap(res, oth.res);
	}

	inline void merge(slope_t &oth) {
		if (pq.size() < oth.pq.size()) swap(oth);

		if (!oth.pq.empty()) {
			if (pq.top() > oth.pq.top())
				res += oth.slp * (pq.top() - oth.pq.top());
			if (pq.top() < oth.pq.top())
				res +=     slp * (oth.pq.top() - pq.top());
		}

		res += oth.res;
		slp += oth.slp;

		for (; !oth.pq.empty(); oth.pq.pop())
			pq.push(oth.pq.top());

	}

	inline void __init__(int v) {
		slp = 1, res = 0;
		pq.push(v), pq.push(v);
	}

	inline void __norm__(int v) {
		for (; slp > 1; slp --) {
			int last = pq.top(); pq.pop();
			res -= (last - pq.top()) * (slp - 1);
		}
		int slp1 = pq.top(); pq.pop();
		int slp0 = pq.top(); pq.pop();
		pq.push(slp0 + v);
		pq.push(slp1 + v);
	}

	inline void print() {
		priority_queue<int> f = pq;
		cout << "pq = { ";
		while (!f.empty())
			cout << f.top() << ' ', f.pop();
		cout << "}\n";
		cout << "slp = " << slp << '\n';
		cout << "ans = " << res << '\n';
	}

} slope_trick[N];

void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 2; i <= n + m; i++)
		cin >> p[i] >> c[i];
	for (int i = n + m; i > 1; i--) {
		// cout << "\nsolve " << i << "\n";
		// slope_trick[i].print();
		if (i > n) {
			slope_trick[i].__init__(c[i]);
		} else {
			slope_trick[i].__norm__(c[i]);
		}
		// slope_trick[i].print();
		slope_trick[p[i]].merge(slope_trick[i]);
	}
	slope_trick[1].__norm__(0);
	cout << slope_trick[1].res << '\n';
}

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