#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
set<vector<int>> st1, st2;
for(int i = 0; i < n; ++i){
st1.insert({i, a[i], 1});
st2.insert({a[i], i, 1});
}
int cnt = 0, sum = 0;
while(cnt < (n + 1) / 2){
auto p2 = prev(st2.end());
int nowi = (*p2)[1];
cnt += (*p2)[2], sum += (*p2)[0];
if((*p2)[2] > 0){
cout << sum << '\n';
}
int dcnt = -(*p2)[2], dsum = -(*p2)[0];
auto p1 = st1.lower_bound(vector<int>{nowi, -(int)1e18, -(int)1e18});
if(p1 != st1.begin()){
auto p1p = prev(p1);
dsum += (*p1p)[1];
dcnt += (*p1p)[2];
st2.erase(st2.find(vector<int>{(*p1p)[1], (*p1p)[0], (*p1p)[2]}));
st1.erase(p1p);
}
auto p1n = next(p1);
if(p1n != st1.end()){
dsum += (*p1n)[1];
dcnt += (*p1n)[2];
st2.erase(st2.find(vector<int>{(*p1n)[1], (*p1n)[0], (*p1n)[2]}));
st1.erase(p1n);
}
st2.insert({dsum, nowi, dcnt});
st1.insert({nowi, dsum, dcnt});
st2.erase(p2);
st1.erase(p1);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
