#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=200005;
ll a[maxn], pre[2][maxn];
set <pll> range, profit;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n;
for (ll i=1; i<=n; i++)
{
cin >> a[i];
pre[i&1][i]=pre[i&1][i-1]+a[i];
pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
}
pre[0][n+1]=pre[0][n], pre[1][n+1]=pre[1][n];
// calculate range sum, index l and r are chosen
auto sum=[&](ll l, ll r)
{
assert((r-l)%2==0); l--, r++;
return pre[r&1][r]-(l?pre[r&1][l-1]:0);
};
for (ll i=1; i<=n; i++) profit.insert({a[i], i});
ll ans=0;
for (ll i=1; i<=(n+1)/2; i++)
{
// cout << "step: " << i << "\n";
// cout << "profit:\n";
// for (auto ptr=profit.begin(); ptr!=profit.end(); ptr++)
// cout << (*ptr).fi << ", " << (*ptr).se << "\n";
// cout << "range:\n";
// for (auto ptr=range.begin(); ptr!=range.end(); ptr++)
// cout << (*ptr).fi << ", " << (*ptr).se << "\n";
// cout << "\n";
auto [x, p]=*prev(profit.end()); profit.erase(prev(profit.end())), ans+=x, cout << ans << "\n";
auto ptr=range.lower_bound(mp(p, 0));
ll l=p, r=p;
if (ptr!=range.end() && (*ptr).fi==p+1)
r=(*ptr).se+1, ptr=range.erase(ptr);
if (ptr!=range.end() && (*ptr).fi==r+2)
r=(*ptr).se, profit.erase({sum((*ptr).fi, (*ptr).se), (*ptr).fi-1}), ptr=range.erase(ptr);
else if (r+1<=n) profit.erase({a[r+1], r+1});
if (ptr!=range.begin() && (*prev(ptr)).se==l-2)
l=(*prev(ptr)).fi, profit.erase({sum((*prev(ptr)).fi, (*prev(ptr)).se), (*ptr).fi-1}), range.erase(prev(ptr));
else if (l-1>=1) profit.erase({a[l-1], l-1});
// cout << "add range:" << l << " " << r << " " << sum(l, r) << "\n\n";
if (l>1 && r<n) profit.insert({sum(l, r), l-1});
range.insert({l, r});
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:25:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
25 | pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
| ~^~
candies.cpp:25:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
25 | pre[i&1^1][i]=pre[i&1^1][i-1]-a[i];
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
