Submission #1246264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246264		duckindog	Candies (JOI18_candies)	C++20	100 / 100	70 ms	8372 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});
    
    a[0] = a[n + 1] = -1'000'000'000'000'000'000;
    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[id]];
        q.push({a[id], id});

        isDel[pre[id]] = isDel[nxt[id]] = true;

        nxt[pre[pre[id]]] = id;
        pre[nxt[nxt[id]]] = id;
        pre[id] = pre[pre[id]];
        nxt[id] = nxt[nxt[id]];

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

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