#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 200200;
ll pref[N], ans, n;
ll get(int l, int r) {
return pref[r - (r == n - 1 ? (r^l)&1 : 0)] - (l > 1 ? pref[l - 2] : 0ll);
}
ll inv(int l, int r) {
return l == r ? 0ll : get(l + 1, r - !((r^l)&1));
}
ll f(pair < int, int > seg) {
auto &[l, r] = seg;
return get(l, r) - inv(l, r);
}
set < pair < int, int > > segs;
set < pair < ll, pair < int, int > > > flips;
void flip(int l, int r) {
auto it = segs.find({l, r}), l_seg = it, r_seg = it;
flips.erase(flips.find({f(*it), *it}));
if(it != segs.begin()) {
-- l_seg;
flips.erase(flips.find({f(*l_seg), *l_seg}));
l = l_seg -> first;
segs.erase(l_seg);
}
++ r_seg;
if(r_seg != segs.end()) {
flips.erase(flips.find({f(*r_seg), *r_seg}));
r = r_seg -> second;
segs.erase(r_seg);
}
segs.erase(it);
segs.insert({l, r});
flips.insert({f({l, r}), {l, r}});
}
main() {
#ifdef Home
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Home
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; ++ i) {
cin >> pref[i];
pref[i] += (i > 1 ? pref[i - 2] : 0ll);
flips.insert({f({i, i}), {i, i}});
segs.insert({i, i});
}
for(int t = (n + 1) / 2; t --> 0;) {
auto [l, r] = flips.rbegin()->second;
//cout << l << ' ' << r << ' ' << flips.rbegin()->first << '\n';
ans += flips.rbegin()->first;
flip(l, r);
/**
for(auto &[val, t] : flips) {
cout << val << ' ' << t.first << ' ' << t.second << '\n';
}
// */
cout << ans << '\n';
}
}
Compilation message
candies.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
