oj.uz

Submission #779767

# Submission time Handle Problem Language Result Execution time Memory
779767 2023-07-11T19:20:41 Z LucaIlie Candies (JOI18_candies) C++17
0 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>

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;

int 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\n";
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -