Submission #67075

#	Time	Username	Problem	Language	Result	Execution time	Memory
67075		aome	Candies (JOI18_candies)	C++17	0 / 100	4 ms	504 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; }
		}
		if (v1 >= v2) {
			int p = pq1.top().l; pq1.pop();
			int l = p, r = p; 
			auto it = s.lower_bound(make_pair(p, 0));
			if (it != s.end() && (it -> first) == r + 2) {
				r = (it -> second), s.erase(it);
			}
			it = s.lower_bound(make_pair(p, 0));
			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));
			}
			res += v1;
		}
		else {
			int l = pq2.top().l, r = pq2.top().r; 
			pq2.pop();
			s.erase(s.find(make_pair(l, r)));
			l--, r++;
			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));				
			}
			res += v2;
		}
		cout << res << '\n';
	}
	
}

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