#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] } );
}
val[0] = val[n + 1] = -1e9;
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 } );
if ( u.l != 1 )
updates.erase( { leftt[u.l - 1], rightt[u.l - 1], val[u.l - 1] } );
if ( u.r != n )
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 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
