#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 2e5 ;
ll n, ans, num, a[N + 1], pref[N + 3] ;
set<pair<ll, ll>> s1, s2 ;
set<pair<ll, pair<ll, ll>>> s ;
ll get_sum(ll l, ll r)
{
if(!l || r > n)return -1e18 ;
ll num = 1 ;
if(l % 2 == 0)num = -1 ;
return (pref[r] - pref[l - 1]) * num ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
for(ll i = 1 ; i <= n ; i++)
{
cin >> a[i] ;
s1.insert({i, i}) ;
s2.insert({-i, -i}) ;
pref[i] = pref[i - 1] ;
if(i % 2)pref[i] += a[i] ;
else pref[i] -= a[i] ;
s.insert({a[i], {i, i}}) ;
}
pref[n + 1] = pref[n] ;
for(ll i = 1 ; i <= (n + 1) / 2 ; i++)
{
// for(auto j : s1)
// cout<<j.fi<<' '<<j.se << '\n' ;
ll num = (*s.rbegin()).fi, l = (*s.rbegin()).se.fi, r = (*s.rbegin()).se.se ;
// cout<<l<<' '<<r << '\n' ;
pair<ll, ll> pz1 = {l, r + 1}, pz2 = {-r - 1, -l - 1} ;
s.erase(*s.rbegin()) ;
s1.erase({l, r}) ;
s2.erase({-r, -l}) ;
if(s1.lower_bound(pz1) != s1.end())
pz1 = *s1.lower_bound({l, r}) ;
if(s2.lower_bound(pz2) != s2.end())
pz2 = *s2.lower_bound({-r, -l}) ;
if(pz1.fi != l)s1.erase(pz1) ;
if(-pz2.se != l)s1.erase({-pz2.se, -pz2.fi}) ;
if(-pz2.fi != r)s2.erase(pz2) ;
if(pz1.se != r)s2.erase({-pz1.se, -pz1.fi}) ;
if(pz1.fi != l)s.erase({get_sum(pz1.fi, pz1.se), {pz1.fi, pz1.se}}) ;
if(-pz2.se != l)s.erase({get_sum(-pz2.se, -pz2.fi), {-pz2.se, -pz2.fi}}) ;
l = -pz2.se ;
r = pz1.se ;
s1.insert({l, r}) ;
s2.insert({-r, -l}) ;
s.insert({get_sum(l, r), {l, r}}) ;
ans += num ;
cout << ans << '\n' ;
}
return 0 ;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
652 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
724 KB |
Output is correct |
| 2 |
Correct |
3 ms |
652 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
