Submission #986137

#	Time	Username	Problem	Language	Result	Execution time	Memory
986137		flappybird	Candies (JOI18_candies)	C++17	100 / 100	190 ms	20880 KiB

candies

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<short, short> pss;
#define MAX 201010
#define MAXS 2200
#define INF 1'000'000'010'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define TC 1
#define MOD 1000000007
ll A[MAX];
ll S[MAX];
int chk[MAX];
ll xs[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	priority_queue<pair<ll, pii>> pq;
	set<int> s;
	//for (i = 1; i <= N; i++) A[i] = rand();
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) pq.emplace(A[i], pii(i, i)), S[i] = S[i - 1] + A[i], s.insert(i);
	xs[1] = A[1];
	xs[2] = A[2];
	for (i = 3; i <= N; i += 2) xs[i] = xs[i - 2] + A[i];
	for (i = 4; i <= N; i += 2) xs[i] = xs[i - 2] + A[i];
	s.insert(0);
	s.insert(N + 1);
	ll x = 0;
	ll sum = 0;
	for (i = 1; i <= (N + 1) / 2; i++) {
		int l, r;
		l = pq.top().second.first;
		r = pq.top().second.second;
		ll v = pq.top().first;
		pq.pop();
		if (chk[l - 1] || chk[r + 1]) {
			i--;
			continue;
		}
		if (chk[l] || chk[r]) {
			i--;
			continue;
		};
		sum += v;
		cout << sum << ln;
		chk[l] = chk[r] = 1;
		s.erase(l);
		s.erase(r);
		if (l == 1 || r == N) continue;
		if (l - 2 >= 1 && chk[l - 2]) {
			auto it = s.lower_bound(l - 2);
			it--;
			l = *it + 1;
		}
		if (r + 2 <= N && chk[r + 2]) {
			auto it = s.lower_bound(r + 2);
			r = *it - 1;
		}
		while (1) {
			auto it = s.lower_bound(l);
			if (it == s.end()) break;
			if (*it <= r) {
				s.erase(it);
				continue;
			}
			break;
		}
		l--;
		r++;
		if (l <= 0) continue;
		if (r > N) continue;
		assert(!((l ^ r) & 1));
		ll nv;
		if (l > 1) nv = xs[r] - xs[l - 2] - (xs[r - 1] - xs[l - 1]);
		else nv = xs[r] - (xs[r - 1] - xs[l - 1]);
		pq.emplace(nv, pii(l, r));
	}
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:40:5: warning: unused variable 'x' [-Wunused-variable]
   40 |  ll x = 0;
      |     ^

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