제출 #1246248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246248		duckindog	Candies (JOI18_candies)	C++20	0 / 100	1 ms	576 KiB

candies

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n;
long long a[N];

bool isDel[N];
int nxt[N], pre[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    iota(nxt + 1, nxt + n + 1, 2);
    iota(pre + 1, pre + n + 1, 0);

    priority_queue<pair<long long, int>> q;
    for (int i = 1; i <= n; ++i) q.push({a[i], i});
    
    long long answer = 0;
    for (int i = 1;  i <= (n + 1) / 2; ++i) { 
        while (q.size() && isDel[q.top().second]) q.pop();
        auto [value, id] = q.top(); q.pop();

        answer += value;
        a[id] = -a[id] + a[pre[id]] + a[nxt[i]];
        q.push({a[id], id});
        isDel[pre[id]] = isDel[nxt[id]] = true;
        nxt[pre[pre[id]]] = id;
        pre[nxt[nxt[id]]] = id;

        cout << answer << "\n";
    }
}

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