Submission #67084

#	Time	Username	Problem	Language	Result	Execution time	Memory
67084		aome	Candies (JOI18_candies)	C++17	100 / 100	465 ms	70060 KiB

candies

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const long long INF = 1e18;

struct Seg {
	int l, r;
	long long w;

	Seg (int l, int r, long long w) :
		l(l), r(r), w(w) {}

	bool operator < (const Seg& rhs) const {
		return w < rhs.w;
	}
};

int n;
int a[N];
long long res;
long long sum[2][N];
vector<Seg> vec;
set< pair<int, int> > s;
priority_queue<Seg> pq1, pq2;

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		sum[0][i] = sum[0][i - 1] + a[i] * (i % 2 == 0);
		sum[1][i] = sum[1][i - 1] + a[i] * (i % 2 == 1);
		pq1.push(Seg(i, i, a[i]));
	}
	for (int i = 1; i <= (n + 1) / 2; ++i) {
		long long v1 = -INF, v2 = -INF;
		while (pq1.size()) {
			long long w = pq1.top().w;
			int p = pq1.top().l;
			auto it = s.lower_bound(make_pair(p + 2, 0));
			if (it != s.begin() && (--it) -> second + 1 >= p) pq1.pop();
			else { v1 = w; break; }
		}
		while (pq2.size()) {
			long long w = pq2.top().w;
			int l = pq2.top().l, r = pq2.top().r;
			if (s.find(make_pair(l, r)) == s.end()) pq2.pop();
			else { v2 = w; break; }
		}
		int l, r;
		res += max(v1, v2);
		if (v1 >= v2) {
			l = pq1.top().l, r = pq1.top().r, pq1.pop();
			// cout << "#add " << l << '\n';
		}
		else {

			l = pq2.top().l, r = pq2.top().r, pq2.pop();
			s.erase(s.find(make_pair(l, r))), l--, r++;
			// cout << "#modify " << l << ' ' << r << '\n';
		}
		auto it = s.lower_bound(make_pair(l, r));
		if (it != s.end() && (it -> first) == r + 2) {
			r = (it -> second), s.erase(it);
		}
		it = s.lower_bound(make_pair(l, r));
		if (it != s.begin() && (--it) -> second == l - 2) {
			l = (it -> first), s.erase(it);
		}
		bool t = l % 2;
		if (l > 1 && r < n) {
			pq2.push(Seg(l, r, (sum[t ^ 1][r + 1] - sum[t ^ 1][l - 2]) - (sum[t][r] - sum[t][l - 1])));
		}
		s.insert(make_pair(l, r));
		// cout << "#\n";
		// for (auto j : s) cout << j.first << ' ' << j.second << '\n';
		cout << res << '\n';
	}
	
}

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