Submission #129911

#	Time	Username	Problem	Language	Result	Execution time	Memory
129911		RockyB	Candies (JOI18_candies)	C++17	100 / 100	1070 ms	29816 KiB

candies

#include <bits/stdc++.h>

#define f first
#define s second

#define sz(x) (int)x.size()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define nl '\n'
#define ioi exit(0);

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 7;

int n;
int a[N];

pair <ll, ll> rev(pair <ll, ll> x) {
	return {x.s, x.f};
}
int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	#ifdef IOI
		freopen ("in.txt", "r", stdin);
		freopen ("A.out", "w", stdout);
	#endif
	cin >> n;
	set < pair <ll, ll > > val, ind;
	rep(i, 1, n) {
		cin >> a[i];
		val.insert({a[i], i});
		ind.insert({i, a[i]});
	}
	ll ans = 0;
	rep(j, 1, (n + 1) / 2) {
		pair <ll, ll> ai = *val.rbegin();
		val.erase(--val.end());
		ind.erase(rev(ai));
		ans += ai.f;
		ll del = -ai.f;
		bool add = 1;
		{
			auto it = ind.upper_bound(rev(ai));
			if (it != ind.end()) {
				del += it -> s;
				ind.erase(it);
				val.erase(rev(*it));
			}
			else add = 0;
		}
		{
			auto it = ind.lower_bound(rev(ai));
			if (it != ind.begin()) {
				--it;
				del += it -> s;
				ind.erase(it);
				val.erase(rev(*it));
			}
			else add = 0;
		}
		if (add) {
			val.insert({del, ai.s});
			ind.insert({ai.s, del});
		}
		cout << ans << endl;
	}

	ioi
}

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