#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
int n;
ll a[N];
int nxt[N], prv[N];
bool del[N];
ll val[N];
void solution () {
cin >> n;
rep (i, 1, n) cin >> a[i];
struct Data {
ll val, l, r;
};
struct cmp {
bool operator () (Data A, Data B) { return A.val < B.val; }
};
priority_queue<Data, vector<Data>, cmp> S;
rep (i, 1, n) {
S.push({a[i], i, i});
nxt[i] = i;
prv[i] = i;
}
nxt[0] = prv[0] = 0;
nxt[n + 1] = prv[n + 1] = n + 1;
ll res = 0;
while (!S.empty()) {
Data cur = S.top();
S.pop();
if (del[cur.l] || del[cur.r] || del[cur.l - 1] || del[cur.r + 1]) continue;
// cout << cur.l <<" "<<cur.r <<"\n";
del[cur.l] = del[cur.r] = 1;
res += cur.val;
if (del[cur.r + 2] || del[cur.l - 2]) {
ll nval = cur.val, added = 0, nl = cur.l - 1, nr = cur.r + 1;
if (del[cur.r + 2]) nval += val[cur.r + 2], added += a[cur.r + 1], nr = nxt[cur.r + 2];
if (del[cur.l - 2]) nval += val[cur.l - 2], added += a[cur.l - 1], nl = prv[cur.l - 2];
val[nl + 1] = val[nr - 1] = nval;
nxt[nl + 1] = nxt[nr - 1] = nr;
prv[nl + 1] = prv[nr - 1] = nl;
// cout <<a[nl] + a[nr] + added - nval <<" "<<nl <<" "<<nr <<"\n";
if (nl > 0 && nr < n + 1)
S.push({a[nl] + a[nr] + added - nval, nl, nr});
}
else {
val[cur.l] = val[cur.r] = cur.val;
nxt[cur.l] = nxt[cur.r] = cur.r + 1;
prv[cur.l] = prv[cur.r] = cur.l - 1;
if (cur.l - 1> 0 && cur.r + 1 < n + 1)
S.push({a[cur.r + 1] + a[cur.l - 1] - cur.val, cur.l - 1, cur.r + 1});
}
cout << res <<"\n";
}
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
