//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'
int n;
vector<ll> a;
multiset<arr(3)> ord , sgs;
ll o = 0;
void uSg(ll l , ll r , ll c){
arr(3) d = {l , r , c};
auto itr = sgs.find(d);
ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]});
vector<arr(3)> dls;
dls.pb({l , r , c});
o += c , c = (-c);
if(itr != sgs.bg()){
--itr;
c += (*itr)[2] , l = (*itr)[0];
ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]}) , dls.pb({(*itr)[0] , (*itr)[1] , (*itr)[2]});
itr++;
}
if(itr != --sgs.end()){
++itr;
c += (*itr)[2] , r = (*itr)[1];
ord.erase({(*itr)[2] , (*itr)[0] , (*itr)[1]}) , dls.pb({(*itr)[0] , (*itr)[1] , (*itr)[2]});
itr--;
}
ord.insert({c , l , r}) , sgs.insert({l , r , c});
for(auto &dl : dls) sgs.erase(dl);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
int d;
cin >> d;
a.pb(d);
}
for(int i = 0 ; i < n ; i++){
sgs.insert({i , i , a[i]}) , ord.insert({a[i] , i , i});
}
for(int i = 1 ; i <= ((n + 1) >> 1) ; i++){
auto itr = --(ord.end());
ll l = (*itr)[1] , c = (*itr)[0] , r = (*itr)[2];
uSg(l , r , c);
cout << o << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
