#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define f first
#define s second
const ll inf = 1e18;
set<pii> s, ord;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin >> n;
for(int i=1; i<=n; i++){
int x;
cin >> x;
s.insert({-x, i});
ord.insert({i, -x});
}
s.insert({inf, 0}), s.insert({inf, n+1});
ord.insert({0, inf}), ord.insert({n+1, inf});
ll ans = 0;
for(int i=0; i<((n+1)>>1); i++){
pii v = *s.begin();
ans -= v.f;
cout << ans << endl;
auto it = ord.lower_bound({v.s, -inf});
--it;
pii a = *it;
s.erase(s.find({a.s, a.f}));
ord.erase(it++);
pii b = *it;
s.erase(s.find({b.s, b.f}));
ord.erase(it++);
pii c = *it;
s.erase(s.find({c.s, c.f}));
ord.erase(it++);
s.insert({a.s+c.s-b.s, b.f});
ord.insert({b.f, a.s+c.s-b.s});
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
580 KB |
Output is correct |
| 2 |
Correct |
3 ms |
592 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
592 KB |
Output is correct |
| 6 |
Correct |
4 ms |
592 KB |
Output is correct |
| 7 |
Correct |
4 ms |
592 KB |
Output is correct |
| 8 |
Correct |
4 ms |
592 KB |
Output is correct |
| 9 |
Correct |
3 ms |
600 KB |
Output is correct |
| 10 |
Correct |
3 ms |
592 KB |
Output is correct |
| 11 |
Correct |
3 ms |
592 KB |
Output is correct |
| 12 |
Correct |
3 ms |
568 KB |
Output is correct |
| 13 |
Correct |
3 ms |
592 KB |
Output is correct |
| 14 |
Correct |
3 ms |
592 KB |
Output is correct |
| 15 |
Correct |
3 ms |
580 KB |
Output is correct |
| 16 |
Correct |
4 ms |
592 KB |
Output is correct |
| 17 |
Correct |
4 ms |
592 KB |
Output is correct |
| 18 |
Correct |
3 ms |
592 KB |
Output is correct |
| 19 |
Correct |
4 ms |
592 KB |
Output is correct |
| 20 |
Correct |
3 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
580 KB |
Output is correct |
| 2 |
Correct |
3 ms |
592 KB |
Output is correct |
| 3 |
Correct |
3 ms |
592 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
592 KB |
Output is correct |
| 6 |
Correct |
4 ms |
592 KB |
Output is correct |
| 7 |
Correct |
4 ms |
592 KB |
Output is correct |
| 8 |
Correct |
4 ms |
592 KB |
Output is correct |
| 9 |
Correct |
3 ms |
600 KB |
Output is correct |
| 10 |
Correct |
3 ms |
592 KB |
Output is correct |
| 11 |
Correct |
3 ms |
592 KB |
Output is correct |
| 12 |
Correct |
3 ms |
568 KB |
Output is correct |
| 13 |
Correct |
3 ms |
592 KB |
Output is correct |
| 14 |
Correct |
3 ms |
592 KB |
Output is correct |
| 15 |
Correct |
3 ms |
580 KB |
Output is correct |
| 16 |
Correct |
4 ms |
592 KB |
Output is correct |
| 17 |
Correct |
4 ms |
592 KB |
Output is correct |
| 18 |
Correct |
3 ms |
592 KB |
Output is correct |
| 19 |
Correct |
4 ms |
592 KB |
Output is correct |
| 20 |
Correct |
3 ms |
592 KB |
Output is correct |
| 21 |
Correct |
652 ms |
28784 KB |
Output is correct |
| 22 |
Correct |
628 ms |
28732 KB |
Output is correct |
| 23 |
Correct |
619 ms |
28656 KB |
Output is correct |
| 24 |
Correct |
354 ms |
28564 KB |
Output is correct |
| 25 |
Correct |
340 ms |
28592 KB |
Output is correct |
| 26 |
Correct |
351 ms |
28576 KB |
Output is correct |
| 27 |
Correct |
353 ms |
28708 KB |
Output is correct |
| 28 |
Correct |
347 ms |
28836 KB |
Output is correct |
| 29 |
Correct |
357 ms |
28696 KB |
Output is correct |
| 30 |
Correct |
353 ms |
28744 KB |
Output is correct |
| 31 |
Correct |
359 ms |
28720 KB |
Output is correct |
| 32 |
Correct |
366 ms |
28772 KB |
Output is correct |
| 33 |
Correct |
523 ms |
28720 KB |
Output is correct |
| 34 |
Correct |
452 ms |
28488 KB |
Output is correct |
| 35 |
Correct |
479 ms |
28556 KB |
Output is correct |
| 36 |
Correct |
624 ms |
28748 KB |
Output is correct |
| 37 |
Correct |
643 ms |
28688 KB |
Output is correct |
| 38 |
Correct |
697 ms |
28660 KB |
Output is correct |
| 39 |
Correct |
348 ms |
28648 KB |
Output is correct |
| 40 |
Correct |
347 ms |
28508 KB |
Output is correct |
| 41 |
Correct |
349 ms |
28524 KB |
Output is correct |
| 42 |
Correct |
357 ms |
28676 KB |
Output is correct |
| 43 |
Correct |
356 ms |
28668 KB |
Output is correct |
| 44 |
Correct |
364 ms |
28864 KB |
Output is correct |
| 45 |
Correct |
386 ms |
28864 KB |
Output is correct |
| 46 |
Correct |
365 ms |
28736 KB |
Output is correct |
| 47 |
Correct |
375 ms |
28712 KB |
Output is correct |
| 48 |
Correct |
472 ms |
28476 KB |
Output is correct |
| 49 |
Correct |
474 ms |
28552 KB |
Output is correct |
| 50 |
Correct |
467 ms |
28552 KB |
Output is correct |
