Submission #114614

#	Time	Username	Problem	Language	Result	Execution time	Memory
114614		maruii	Candies (JOI18_candies)	C++14	0 / 100	4 ms	512 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
#define ff first
#define ss second

int L[200005], R[200005];
ll A[200005], ans;
set<pli> s;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i], s.insert(pli(A[i], i));
	iota(L + 1, L + N + 1, 0);
	iota(R + 1, R + N + 1, 2);

	for (int i = 0; i < (N + 1 >> 1); ++i) {
		auto a = s.end();
		--a;
		int x = a->ss;
		ans += A[x];
		cout << ans << '\n';
		s.erase(a);
		A[x] = A[L[x]] + A[R[x]] - A[x];
		s.erase(pli(A[L[x]], L[x]));
		s.erase(pli(A[R[x]], R[x]));
		s.insert(pli(A[x], x));
		L[x] = L[L[x]];
		R[L[x]] = x;
		R[x] = R[R[x]];
		L[R[x]] = x;
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:19:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for (int i = 0; i < (N + 1 >> 1); ++i) {
                       ~~^~~

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