Submission #715656

#	Time	Username	Problem	Language	Result	Execution time	Memory
715656		fatemetmhr	Candies (JOI18_candies)	C++17	100 / 100	387 ms	22624 KiB

candies

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

set <pair<ll, int>> seg, av;
ll a[maxn5], sum[maxn5], have[maxn5];
int pre[maxn5], l[maxn5], r[maxn5], nxt[maxn5];

inline int merge(int v){
    int u = nxt[v];
    int z = nxt[u];
    nxt[v] = z;
    if(z != -1)
        pre[z] = v;
    av.erase({-(sum[u] - 2 * have[u]), u});
    av.erase({-(sum[v] - 2 * have[v]), v});
    sum[v] += sum[u];
    have[v] += have[u];
    l[v] = min(l[v], l[u]);
    r[v] = max(r[v], r[u]);
    return v;
}

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

    int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> sum[i];
        av.insert({-sum[i], i});
        l[i] = r[i] = i;
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n - 1] = -1;
    ll cur = 0;
    for(int i = 1; i <= (n + 1) / 2; i++){
        int v = av.begin()->se;
        av.erase(av.begin());
        cur += sum[v] - 2 * have[v];
        have[v] = sum[v] - have[v];
        if(nxt[v] != -1)
            v = merge(v);
        if(pre[v] != -1)
            v = merge(pre[v]);
        if((r[v] - l[v] + 1) & 1)
            av.insert({-(sum[v] - 2 * have[v]), v});
        cout << cur << '\n';
    }
}

/*
5
3 5 1 7 6
*/

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