제출 #1165809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165809		MateiKing80	Candies (JOI18_candies)	C++20	큐에 대기중	0 ms	0 KiB

candies

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

#define pii pair<ll, ll>
#define fr first
#define sc second
 
const int N = 2e5 + 10;
  
int n, L[N], R[N];
int A[N];
set<pii> S;
 
signed main() 
{
	cin >> n;
	for (int i = 1 ; i <= n ; i ++) 
	{
		cin >> A[i];
		if(i > 1) 
			L[i] = i - 1;
		if(i < n) 
			R[i] = i + 1;
		S.emplace(A[i], i);
	}
	int ans = 0;
	for (int i = 1; i <= (n + 1) / 2 ; i ++) 
	{
		int now = S.rbegin()->sc;
		ans += A[now];
		cout << ans << "\n";
		S.erase(pii(A[now], now));
		int l = L[now], r = R[now];
		if(l) 
			S.erase(pii(A[l], l));
		if(r) 
			S.erase(pii(A[r], r));
		A[now] = A[l] + A[r] - A[now];
		if(l && r) 
		{
			L[now] = L[l], R[now] = R[r];
			S.emplace(A[now], now);
		} 
		else 
			now = 0;
		if(L[l]) 
			R[L[l]] = now;
		if(R[r]) 
			L[R[r]] = now;
	}
}