Submission #1247852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247852		chikien2009	Candies (JOI18_candies)	C++20	100 / 100	65 ms	8388 KiB

candies

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, l[200002], r[200002], p;
long long a[200002], x, res;
bool covered[200002];
priority_queue<pair<long long, int>> pq;

int main()
{
    setup();

    cin >> n;
    l[0] = 0;
    r[n + 1] = n + 1;
    a[0] = a[n + 1] = -1e18;
    for (int i = 1; i <= n; ++i)
    {
        l[i] = i - 1;
        r[i] = i + 1;
        cin >> a[i];
        pq.push({a[i], i});
    }
    for (int i = 1; i <= (n + 1) / 2; ++i)
    {
        while (covered[pq.top().second])
        {
            pq.pop();
        }
        x = pq.top().first;
        p = pq.top().second;
        pq.pop();
        res += x;
        a[p] = a[l[p]] + a[r[p]] - a[p];
        covered[l[p]] = covered[r[p]] = true;
        r[p] = r[r[p]];
        l[p] = l[l[p]];
        l[r[p]] = r[l[p]] = p;
        pq.push({a[p], p});
        cout << res << "\n";
    }
    return 0;
}

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