Submission #779772

#	Time	Username	Problem	Language	Result	Execution time	Memory
779772		LucaIlie	Candies (JOI18_candies)	C++17	0 / 100	2 ms	468 KiB

candies

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct update {
    int l, r;
    long long val;

    bool operator < ( const update &u ) const {
        if ( val == u.val )
            return l < u.l;
        return val > u.val;
    }
};

const int MAX_N = 2e5;
int leftt[MAX_N + 2], rightt[MAX_N + 2];
long long v[MAX_N + 2], val[MAX_N + 2];
set<update> updates;

signed main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> v[i];
        val[i] = v[i];
        leftt[i] = rightt[i] = i;
        updates.insert( { i, i, v[i] } );
    }
    leftt[0] = 1;
    rightt[n + 1] = n;

    long long sum = 0;
    for ( int k = 1; k <= (n + 1) / 2; k++ ) {
        update u = *updates.begin();
        sum += u.val;

        updates.erase( { u.l, u.r, u.val } );
        updates.erase( { leftt[u.l - 1], rightt[u.l - 1], val[u.l - 1] } );
        updates.erase( { leftt[u.r + 1], rightt[u.r + 1], val[u.r + 1] } );

        u.val = -u.val + val[u.l - 1] + val[u.r + 1];
        u.l = leftt[u.l - 1];
        u.r = rightt[u.r + 1];
        leftt[u.l] = leftt[u.r] = u.l;
        rightt[u.l] = rightt[u.r] = u.r;
        val[u.l] = val[u.r] = u.val;

        updates.insert( u );

        cout << sum << "\n";
    }

    return ( n <= 10);
}

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