#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<long long> ps[2];
for (int rep = 0; rep < 2; ++rep) {
ps[rep].resize(n);
for (int i = 0; i < n; ++i) {
if (i % 2 != rep % 2) {
ps[rep][i] = (i ? ps[rep][i - 1] : 0);
continue;
}
ps[rep][i] = a[i];
if (i) ps[rep][i] += ps[rep][i - 1];
}
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
return a[i] > a[j];
});
set<pair<int, int>> se;
auto get_val = [&](int l, int r) {
long long ret = 0;
if (l % 2 == r % 2) {
int pr = l % 2;
return make_pair(ps[pr][r] - (l ? ps[pr][l - 1] : 0), (r - l + 2) / 2);
}
ret = ps[1][r] - (l ? ps[1][l - 1] : 0);
ret = max(ret, ps[0][r] - (l ? ps[0][l - 1] : 0));
return make_pair(ret, (r - l + 1) / 2);
};
int ones = 0;
long long res = 0;
auto edit = [&](int i) {
auto it = se.lower_bound(make_pair(i, -1));
bool nx = false, pre = false;
if (it != se.end() && it->first == i + 1) {
nx = true;
}
if (it != se.begin() && prev(it)->second == i - 1) {
pre = true;
}
if (pre && nx) {
int l = prev(it)->first;
auto [x, y] = get_val(l, prev(it)->second);
se.erase(prev(it));
res -= x;
ones -= y;
int r = it->second;
auto [xx, yy] = get_val(it->first, r);
res -= xx;
ones -= yy;
se.erase(it);
se.emplace(l, r);
auto [xxx, yyy] = get_val(l, r);
res += xxx;
ones += yyy;
} else if (pre) {
int l = prev(it)->first;
auto [x, y] = get_val(l, prev(it)->second);
res -= x;
ones -= y;
se.erase(prev(it));
int r = i;
se.emplace(l, r);
auto [xxx, yyy] = get_val(l, r);
res += xxx;
ones += yyy;
} else if (nx) {
int l = i;
int r = it->second;
auto [xx, yy] = get_val(it->first, r);
res -= xx;
ones -= yy;
se.erase(it);
se.emplace(l, r);
auto [xxx, yyy] = get_val(l, r);
res += xxx;
ones += yyy;
} else {
se.insert({i, i});
res += a[i];
ones++;
}
};
int pq = 1;
vector<long long> ans((n + 1) / 2 + 1);
for (int i = 0; i < n; ++i) {
int j = i;
while (j < n && a[id[j]] == a[id[i]]) {
edit(id[j]);
j++;
}
while (pq <= ones && pq <= (n + 1) / 2) {
ans[pq] = res;
pq++;
}
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
