#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
// chiar asa de prost implementez sau e gresit? :(
using namespace std;
template<class T, class Container = vector<T>, class Compare = less<T>>
struct PriorityQueue {
int sz = 0;
priority_queue<T, Container, Compare> pq, del;
void emplace(const T &val) { pq.emplace(val); ++sz; }
void erase(const T &val) { del.emplace(val); --sz; }
void pop() { erase(top()); }
T top() {
while (!del.empty() && !pq.empty() && del.top() == pq.top()) del.pop(), pq.pop();
return pq.top();
}
int size() const {return sz;}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
PriorityQueue<tuple<int64_t, int64_t, int64_t>> interv;
for (int i = 0; i < n; ++i) {
interv.emplace(make_tuple(v[i], i, i));
}
vector<int64_t> lft(n), rgt(n), val(n);
for (int i = 0; i < n; ++i) {
lft[i] = i;
rgt[i] = i;
val[i] = v[i];
}
function<int64_t(int64_t)> Left = [&](int64_t x) {
if (lft[x] == x) return x;
return lft[x] = Left(lft[x]);
};
function<int64_t(int64_t)> Right = [&](int64_t x) {
if (rgt[x] == x) return x;
return rgt[x] = Right(rgt[x]);
};
int64_t ans = 0;
for (int k = 1; k <= (n + 1) / 2; ++k) {
int64_t curr, l, r; tie(curr, l, r) = interv.top(); interv.pop();
ans += curr;
cout << ans << '\n';
curr = -curr;
int64_t nl = l, nr = r;
if (l - 1 >= 0) {
int64_t x = Left(l - 1), y = l - 1;
interv.erase(make_tuple(val[x], x, y));
curr += val[x];
nl = x;
}
if (r + 1 < n) {
int64_t x = r + 1, y = Right(x);
interv.erase(make_tuple(val[x], x, y));
curr += val[x];
nr = y;
}
interv.emplace(make_tuple(curr, nl, nr));
val[nl] = curr;
lft[nr] = nl;
rgt[nl] = nr;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
