Submission #160162

#	Time	Username	Problem	Language	Result	Execution time	Memory
160162		combi1k1	Candies (JOI18_candies)	C++14	100 / 100	723 ms	27488 KiB

candies

#include<bits/stdc++.h>

using namespace std;

#define ll  long long

#define FOR(i,a,b)  for(int i = a ; i <= b ; ++i)

const int   N   = 2e5 + 1;

typedef pair<ll,int>    ii;

set<ii>  S1;
set<int> S2;

ll  a[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    ll  ans = 0;

    FOR(i,1,n)  {
        cin >> a[i];
        S1.insert({a[i],i});
        S2.insert(i);
    }
    S2.insert(0);
    S2.insert(N);
    FOR(i,1,(n + 1) / 2)    {
        int j = (*--S1.end()).second;

        ans += a[j];
        cout << ans << "\n";

        S1.erase(ii(a[j],j));
        S2.erase(j);

        a[j] = -a[j];

        auto L = S2.upper_bound(j);
        auto R = L--;

        int cnt = 0;

        if (*L >= 1)    {
            a[j] += a[*L];
            S1.erase(ii(a[*L],*L));
            S2.erase(*L);
            cnt++;
        }
        if (*R <= n)    {
            a[j] += a[*R];
            S1.erase(ii(a[*R],*R));
            S2.erase(*R);
            cnt++;
        }
        if (cnt == 2)
            S1.insert(ii(a[j],j)),
            S2.insert(j);
    }
}

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