Submission #1260238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260238		tvgk	Candies (JOI18_candies)	C++20	100 / 100	197 ms	19160 KiB

candies

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int n;
ll a[mxN];
ii dsu[mxN];
set<ii> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dsu[i] = {i, i};
        s.insert({a[i], i});
    }
    dsu[n + 1] = {n + 1, n + 1};

    ll ans = 0;
    while (s.size())
    {
        ii j = *s.rbegin();
        s.erase(j);

        ans += j.fi;
        cout << ans << '\n';

        int u = dsu[dsu[j.se].fi - 1].fi;
        int v = dsu[j.se].se + 1;
        s.erase({a[u], u});
        s.erase({a[v], v});

        a[u] += a[v] - j.fi;
        v = dsu[v].se;
        dsu[u].se = v;
        dsu[v].fi = u;

        if (u && v <= n)
            s.insert({a[u], u});
    }
}

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