Submission #1310398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310398		sebokx	Candies (JOI18_candies)	C++20	100 / 100	72 ms	10088 KiB

candies

#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;
using ll = long long;

#define int ll

const int N = 200'007;
int n;

ll t[N];
int lefts[N];
int rights[N];
bool blocked[N];
priority_queue<pair<ll, int>> que;

ll solve(){
    pair<ll, int> top = que.top();

    while(blocked[top.nd]){
        que.pop();
        top = que.top();
    }
    que.pop();

    ll new_val = -top.st;
    if(lefts[top.nd] != -1){
        blocked[lefts[top.nd]] = true;
        new_val += t[lefts[top.nd]];

        lefts[top.nd] = lefts[lefts[top.nd]];
        if(lefts[top.nd] != -1) rights[lefts[top.nd]] = top.nd;
    }
    if(rights[top.nd] != -1){
        blocked[rights[top.nd]] = true;
        new_val += t[rights[top.nd]];

        rights[top.nd] = rights[rights[top.nd]];
        if(rights[top.nd] != -1) lefts[rights[top.nd]] = top.nd;
    }

    t[top.nd] = new_val;
    que.push({new_val, top.nd});

    return top.st;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> t[i];
    t[0] = -1e12;
    t[n+1] = -1e12;

    for(int i = 1; i <= n; i++){
        lefts[i] = i-1;
        rights[i] = i+1;
    }

    for(int i = 1; i <= n; i++) que.push({t[i], i});

    ll ans = 0LL;
    for(int i = 0; i < (n+1)/2; i++){
        ans += solve();
        cout << ans << '\n';
    }

    return 0;
}

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