#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long INF = 1e18;
struct Seg {
int l, r;
long long w;
Seg (int l, int r, long long w) :
l(l), r(r), w(w) {}
bool operator < (const Seg& rhs) const {
return w < rhs.w;
}
};
int n;
int a[N];
long long res;
long long sum[2][N];
vector<Seg> vec;
set< pair<int, int> > s;
priority_queue<Seg> pq1, pq2;
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
sum[0][i] = sum[0][i - 1] + a[i] * (i % 2 == 0);
sum[1][i] = sum[1][i - 1] + a[i] * (i % 2 == 1);
pq1.push(Seg(i, i, a[i]));
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
long long v1 = -INF, v2 = -INF;
while (pq1.size()) {
long long w = pq1.top().w;
int p = pq1.top().l;
auto it = s.lower_bound(make_pair(p + 2, 0));
if (it != s.begin() && (--it) -> second + 1 >= p) pq1.pop();
else { v1 = w; break; }
}
while (pq2.size()) {
long long w = pq2.top().w;
int l = pq2.top().l, r = pq2.top().r;
if (s.find(make_pair(l, r)) == s.end()) pq2.pop();
else { v2 = w; break; }
}
int l, r;
res += max(v1, v2);
if (v1 >= v2) {
l = pq1.top().l, r = pq1.top().r, pq1.pop();
// cout << "#add " << l << '\n';
}
else {
l = pq2.top().l, r = pq2.top().r, pq2.pop();
s.erase(s.find(make_pair(l, r))), l--, r++;
// cout << "#modify " << l << ' ' << r << '\n';
}
auto it = s.lower_bound(make_pair(l, r));
if (it != s.end() && (it -> first) == r + 2) {
r = (it -> second), s.erase(it);
}
it = s.lower_bound(make_pair(l, r));
if (it != s.begin() && (--it) -> second == l - 2) {
l = (it -> first), s.erase(it);
}
bool t = l % 2;
if (l > 1 && r < n) {
pq2.push(Seg(l, r, (sum[t ^ 1][r + 1] - sum[t ^ 1][l - 2]) - (sum[t][r] - sum[t][l - 1])));
s.insert(make_pair(l, r));
}
// cout << "#\n";
// for (auto j : s) cout << j.first << ' ' << j.second << '\n';
cout << res << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
