Submission #486616

#	Time	Username	Problem	Language	Result	Execution time	Memory
486616		ez_ioi	Candies (JOI18_candies)	C++17	0 / 100	2 ms	460 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 2e5 + 5, mod = 1e9 + 7, LOG = 20;

int n;
pair <int, int> cons[mxN];
ll a[mxN];

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	set <pair <ll, int> > st;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		cons[i] = {i - 1, i + 1};
		st.insert({a[i], i});
	}
	ll ans = 0;
	for (int i = 1; i <= (n + 1) / 2; ++i) {
		auto x = *(--st.end());
		ans += x.first;
		st.erase(x);
		int lb = cons[x.second].first, rb = cons[x.second].second;
		if (lb) st.erase({a[lb], lb}); 
		if (rb <= n) st.erase({a[rb], rb}); 
		//if (lb && rb && rb <= n) {
			a[x.second] = a[lb] + a[rb] - a[x.second];
			st.insert({a[x.second], x.second});
			cons[x.second] = {cons[lb].first, cons[rb].second};
			cons[cons[lb].first].second = x.second;
			cons[cons[rb].second].first = x.second;
		/*}
		else {
			cons[cons[lb].first].second = cons[rb].second;
			cons[cons[rb].second].first = cons[lb].first;
		}*/
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92