Submission #1046561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046561		underwaterkillerwhale	Candies (JOI18_candies)	C++17	100 / 100	68 ms	15308 KiB

candies

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;

int n;
ll a[N];
int nxt[N], prv[N];
bool del[N];
ll val[N];

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
    struct Data {
        ll val, l, r;
    };
    struct cmp {
        bool operator () (Data A, Data B) { return A.val < B.val; }
    };
    priority_queue<Data, vector<Data>, cmp> S;
    rep (i, 1, n) {
        S.push({a[i], i, i});
        nxt[i] = i;
        prv[i] = i;
    }
    nxt[0] = prv[0] = 0;
    nxt[n + 1] = prv[n + 1] = n + 1;
    ll res = 0;
    while (!S.empty()) {
        Data cur = S.top();
        S.pop();
        if (del[cur.l] || del[cur.r] || del[cur.l - 1] || del[cur.r + 1]) {
            continue;
        }
//        cout << cur.l <<" "<<cur.r <<"\n";
        del[cur.l] = del[cur.r] = 1;
        res += cur.val;
        if (del[cur.r + 2] || del[cur.l - 2]) {
            ll nval = cur.val, added = 0, nl = cur.l - 1, nr = cur.r + 1;
            if (del[cur.r + 2]) nval += val[cur.r + 2], added += a[cur.r + 1], nr = nxt[cur.r + 2];
            if (del[cur.l - 2]) nval += val[cur.l - 2], added += a[cur.l - 1], nl = prv[cur.l - 2];
            val[nl + 1] = val[nr - 1] = nval - added;
            nxt[nl + 1] = nxt[nr - 1] = nr;
            prv[nl + 1] = prv[nr - 1] = nl;
//            cout <<a[nl] + a[nr] + added - nval <<" "<<nl <<" "<<nr <<"\n";
            if (nl > 0 && nr < n + 1)
                S.push({a[nl] + a[nr] + added - nval, nl, nr});
        }
        else {
            val[cur.l] = val[cur.r] = cur.val;
            nxt[cur.l] = nxt[cur.r] = cur.r + 1;
            prv[cur.l] = prv[cur.r] = cur.l - 1;
            if (cur.l - 1 > 0 && cur.r + 1 < n + 1)
                S.push({a[cur.r + 1] + a[cur.l - 1] - cur.val, cur.l - 1, cur.r + 1});
        }
        cout << res  <<"\n";
    }
}


#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/

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