#include <bits/stdc++.h>
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const ll NN = 1e10 + 7;
const int N = 2e5 + 7;
const int M = 6;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
int n;
int p[N];
ll a[N];
int l[N];
int r[N];
set < pair < ll , ll > > ss;
int get( int x )
{
return (p[x] == x ? x : p[x] = get(p[x]));
}
void solve1()
{
cin >> n;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
p[i] = i;
l[i] = r[i] = i;
ss.insert({ a[i] , i });
}
ll ans = 0;
for( int i = 1; i <= (n + 1) / 2; i++ ){
assert( !ss.empty() );
auto x = *(--ss.end());
ss.erase(--ss.end());
ans += x.fi;
cout << ans << " ";
int l1 = get( l[x.se] - 1 );
int r1 = get( r[x.se] + 1 );
if( l1 != 0 ){
ss.erase({ a[l1] , l1 });
}
if( r1 != 0 ){
ss.erase({ a[r1] , r1 });
}
int f = get( x.se );
ll mz = a[l1] + a[r1] - x.fi;
p[l1] = f;
p[r1] = f;
a[f] = mz;
l[f] = min({ l[f] , l[l1] , l[r1] });
r[f] = max({ r[f] , r[l1] , r[r1] });
f = get( f );
if( l[f] != 0 && r[f] != 0 ){
ss.insert({ mz , f });
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int cghf = 1;//cin >> cghf;
while( cghf-- ){
solve1();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| 4 |
Correct |
6 ms |
512 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
512 KB |
Output is correct |
| 9 |
Correct |
6 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
512 KB |
Output is correct |
| 11 |
Correct |
6 ms |
512 KB |
Output is correct |
| 12 |
Correct |
6 ms |
512 KB |
Output is correct |
| 13 |
Correct |
6 ms |
512 KB |
Output is correct |
| 14 |
Correct |
7 ms |
512 KB |
Output is correct |
| 15 |
Correct |
6 ms |
512 KB |
Output is correct |
| 16 |
Correct |
6 ms |
512 KB |
Output is correct |
| 17 |
Correct |
6 ms |
384 KB |
Output is correct |
| 18 |
Correct |
7 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
6 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| 4 |
Correct |
6 ms |
512 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
512 KB |
Output is correct |
| 9 |
Correct |
6 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
512 KB |
Output is correct |
| 11 |
Correct |
6 ms |
512 KB |
Output is correct |
| 12 |
Correct |
6 ms |
512 KB |
Output is correct |
| 13 |
Correct |
6 ms |
512 KB |
Output is correct |
| 14 |
Correct |
7 ms |
512 KB |
Output is correct |
| 15 |
Correct |
6 ms |
512 KB |
Output is correct |
| 16 |
Correct |
6 ms |
512 KB |
Output is correct |
| 17 |
Correct |
6 ms |
384 KB |
Output is correct |
| 18 |
Correct |
7 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
6 ms |
512 KB |
Output is correct |
| 21 |
Correct |
363 ms |
20216 KB |
Output is correct |
| 22 |
Correct |
553 ms |
20216 KB |
Output is correct |
| 23 |
Correct |
388 ms |
20344 KB |
Output is correct |
| 24 |
Correct |
181 ms |
20088 KB |
Output is correct |
| 25 |
Correct |
184 ms |
20088 KB |
Output is correct |
| 26 |
Correct |
156 ms |
20088 KB |
Output is correct |
| 27 |
Correct |
168 ms |
20216 KB |
Output is correct |
| 28 |
Correct |
166 ms |
20216 KB |
Output is correct |
| 29 |
Correct |
173 ms |
20344 KB |
Output is correct |
| 30 |
Correct |
176 ms |
20344 KB |
Output is correct |
| 31 |
Correct |
191 ms |
20216 KB |
Output is correct |
| 32 |
Correct |
198 ms |
20472 KB |
Output is correct |
| 33 |
Correct |
265 ms |
20092 KB |
Output is correct |
| 34 |
Correct |
250 ms |
19960 KB |
Output is correct |
| 35 |
Correct |
255 ms |
20088 KB |
Output is correct |
| 36 |
Correct |
355 ms |
20216 KB |
Output is correct |
| 37 |
Correct |
428 ms |
20216 KB |
Output is correct |
| 38 |
Correct |
363 ms |
20344 KB |
Output is correct |
| 39 |
Correct |
182 ms |
20064 KB |
Output is correct |
| 40 |
Correct |
153 ms |
20088 KB |
Output is correct |
| 41 |
Correct |
163 ms |
20216 KB |
Output is correct |
| 42 |
Correct |
172 ms |
20216 KB |
Output is correct |
| 43 |
Correct |
171 ms |
20216 KB |
Output is correct |
| 44 |
Correct |
184 ms |
20216 KB |
Output is correct |
| 45 |
Correct |
185 ms |
20312 KB |
Output is correct |
| 46 |
Correct |
175 ms |
20216 KB |
Output is correct |
| 47 |
Correct |
179 ms |
20344 KB |
Output is correct |
| 48 |
Correct |
266 ms |
20044 KB |
Output is correct |
| 49 |
Correct |
267 ms |
20216 KB |
Output is correct |
| 50 |
Correct |
264 ms |
19960 KB |
Output is correct |
