#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int N, tot, A[200005], P[200005][2];
set<iii> s1, r1;
set<tuple<ii, int, int> > s2;
ii rmq(int l, int r) {
ii ret = mp(LLONG_MIN, LLONG_MIN);
for (int i = l; i <= r; i++) ret = max(ret, mp(A[i], i));
return ret;
}
void tks1() {
vector<set<iii>::iterator> td;
assert(!s1.empty());
auto [v, l, r] = *s1.rbegin();
assert(l != 1 && r != N);
s1.erase(--s1.end());
tot += v;
int newl = l - 1, newr = r + 1;
auto it = r1.find(mt(l, r, v));
assert(it != r1.end());
++it;
if (it != r1.end() && g0(*it) == newr + 2) {
newr = g1(*it);
td.pb(it);
if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
}
--it;
if (it != r1.begin()) {
--it;
if (g1(*it) == newl - 2) {
newl = g0(*it);
td.pb(it);
if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
}
++it;
}
for (auto i : td) r1.erase(i);
assert((newl & 1) == (newr & 1));
if (newl == 1 || newr == N) {
r1.emplace(newl, newr, -1ll);
} else {
int nv = (P[newr + 1][(newr + 1) & 1] - P[newl - 2][(newr + 1) & 1]) - (P[newr + 1][newr & 1] - P[newl - 2][newr & 1]);
s1.emplace(nv, newl, newr);
r1.emplace(newl, newr, nv);
}
}
void tks2() {
vector<set<iii>::iterator> td;
assert(!s2.empty());
auto [v, l, r] = *s2.rbegin();
s2.erase(--s2.end());
tot += v.first;
if (l <= v.second - 2) {
s2.emplace(rmq(l, v.second - 2), l, v.second - 2);
}
if (v.second + 2 <= r) {
s2.emplace(rmq(v.second + 2, r), v.second + 2, r);
}
int newl = v.second, newr = v.second;
auto it = r1.lower_bound(mt(newl, 0ll, 0ll));
if (it != r1.end() && g0(*it) == newr + 2) {
newr = g1(*it);
td.pb(it);
if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
}
if (it != r1.begin()) {
--it;
if (g1(*it) == newl - 2) {
newl = g0(*it);
td.pb(it);
if (s1.find(mt(g2(*it), g0(*it), g1(*it))) != s1.end()) s1.erase(mt(g2(*it), g0(*it), g1(*it)));
}
}
for (auto i : td) r1.erase(i);
assert((newl & 1) == (newr & 1));
if (newl == 1 || newr == N) {
r1.emplace(newl, newr, -1ll);
} else {
int nv = (P[newr + 1][(newr + 1) & 1] - P[newl - 2][(newr + 1) & 1]) - (P[newr + 1][newr & 1] - P[newl - 2][newr & 1]);
s1.emplace(nv, newl, newr);
r1.emplace(newl, newr, nv);
}
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
P[i][0] = (i & 1 ? 0 : A[i]) + P[i - 1][0];
P[i][1] = (i & 1 ? A[i] : 0) + P[i - 1][1];
}
s2.emplace(rmq(1, N), 1, N);
for (int i = 1; i <= (N + 1) / 2; i++) {
if (s1.empty()) {
tks2();
} else if (s2.empty()) {
tks1();
} else {
if (g0(*s1.rbegin()) > g0(*s2.rbegin()).first) {
tks1();
} else {
tks2();
}
}
cout << tot << '\n';
}
}
Compilation message
candies.cpp:113:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
113 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
