Submission #47922

#	Time	Username	Problem	Language	Result	Execution time	Memory
47922		cheater2k	Candies (JOI18_candies)	C++17	100 / 100	747 ms	33460 KiB

candies

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

const int N = 200005;

struct segment {
	int l; int r;
	long long real; long long hidden;
	segment(int l=0, int r=0, long long real=0, long long hidden=0): 
		l(l), r(r), real(real), hidden(hidden) {}
	bool operator < (const segment &other) const {
		return l < other.l || (l == other.l && r < other.r);
	}
};

set <segment> s;
set < pair<long long, pair<int,int> > > pq;
int n, a[N];
long long res;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	s.insert(segment(0, 0, 0, 0));
	s.insert(segment(n + 1, n + 1, 0, 0));
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		s.insert(segment(i, i, 0, a[i]));
		pq.insert(make_pair(a[i], make_pair(i, i)));
	}

	for (int have = 1; have <= (n + 1) / 2; ++have) {
		auto top = (*pq.rbegin()); pq.erase(--pq.end());
		res += top.first;
		
		// update the current segment
		set <segment>::iterator it = s.lower_bound(segment(top.second.first, top.second.second));
		auto cur = (*it);
		swap(cur.real, cur.hidden);

		set <segment>::iterator prv, nxt;

		if (it != s.begin()) {
			prv = prev(it);
			cur.real += (prv -> real); cur.hidden += (prv -> hidden); cur.l = (prv -> l);
			pq.erase(make_pair(prv -> hidden - prv -> real, make_pair(prv -> l, prv -> r)));
		}
		if (it != --s.end()) {
			nxt = next(it);
			cur.real += (nxt ->real); cur.hidden += (nxt -> hidden); cur.r = (nxt -> r);
			pq.erase(make_pair(nxt -> hidden - nxt -> real, make_pair(nxt -> l, nxt -> r)));
		}

		if (it != s.begin()) s.erase(prv);
		if (it != --s.end()) s.erase(nxt);
		s.erase(it);

		s.insert(cur);
		if (cur.l != 0 && cur.r != n + 1) {
			// we cannot increase the number of chosen cells with this type of segment
			pq.insert(make_pair(cur.hidden - cur.real, make_pair(cur.l, cur.r)));
		}

		printf("%lld\n", res);
	}
}

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