Submission #1158558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158558		alir3za_zar3	Candies (JOI18_candies)	C++20	100 / 100	63 ms	9972 KiB

candies

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long
#define     pii     pair<int,int>

const int mxN = 5e5+7 , Inf = 1e17;
int n , v[mxN] , l[mxN],r[mxN];
bool mrk[mxN]; 
priority_queue<pii> pq;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> v[i];
    v[0] = v[n+1] = -Inf;
    for (int i=1; i<=n; i++)
        l[i]=i-1 , r[i]=i+1;
    for (int i=1; i<=n; i++)
        pq.push({ v[i] , i });
    
    int k = n+1>>1 , out = 0;
    for (int i=1; i<=k; i++)
    {
        while (!pq.empty())
        {
            auto [q , id] = pq.top();
            pq.pop();
            if (mrk[ id ]) continue;
            
            out += q;
            int lc = l[id] , rc = r[id];
            mrk[lc] = mrk[rc] = true;
            v[id] = v[lc]+v[rc] - v[id];
            pq.push({ v[id] , id });
            l[id] = l[lc]; r[id] = r[rc];
            r[l[id]] = id; l[r[id]] = id;
            break;
        }
        cout << out << '\n';
    }
}

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