#include <iostream>
#include <algorithm>
#include <vector>
const int ms = 200200;
int size[ms][2];
long long sum[ms][2], tot = 0;
int par[ms];
long long getVal(int x) {
if(size[x][0] == size[x][1]) {
return std::max(sum[x][0], sum[x][1]);
} else {
return sum[x][size[x][0] > size[x][1] ? 0 : 1];
}
}
int totS = 0;
int getPar(int x) { return par[x] == x ? x : par[x] = getPar(par[x]); }
void makeUnion(int a, int b) {
a = getPar(a);
b = getPar(b);
if(a == b) return;
tot -= getVal(a);
tot -= getVal(b);
totS -= std::max(size[a][0], size[a][1]);
totS -= std::max(size[b][0], size[b][1]);
size[a][0] += size[b][0];
size[a][1] += size[b][1];
sum[a][0] += sum[b][0];
sum[a][1] += sum[b][1];
tot += getVal(a);
totS += std::max(size[a][0], size[a][1]);
par[b] = a;
}
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> a(n);
std::vector<int> p(n);
for(int i = 0; i < n; i++) {
p[i] = i;
std::cin >> a[i];
par[i] = -1;
}
std::sort(p.begin(), p.end(), [&](int p1, int p2) { return a[p1] > a[p2]; });
std::vector<int> ans((n + 1) / 2, -1);
for(auto x : p) {
totS++;
par[x] = x;
size[x][x % 2] = 1;
sum[x][x % 2] = a[x];
tot += a[x];
if(x > 0 && par[x - 1] != -1) {
makeUnion(x, x - 1);
}
if(x < n - 1 && par[x + 1] != -1) {
makeUnion(x, x + 1);
}
ans[totS - 1] = tot;
}
for(int i = 0; i < (int) ans.size(); i++) {
std::cout << ans[i] << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
