#include <iostream>
#include <vector>
#include <algorithm>
#define ff first
#define ss second
#define ll long long
using namespace std;
ll n;
template <
class NodeType, NodeType (*combine)(NodeType, NodeType), NodeType (*unit)(),
class TagType, NodeType (*mapping)(NodeType, TagType), TagType (*compose)(TagType, TagType)
>
struct LazySegmentTree {
#define m ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
vector<NodeType> arr;
vector<NodeType> st;
vector<TagType> lz;
ll n;
void build(ll _n) {
build(_n, vector<NodeType>(_n+1, unit()));
}
template <class ArrType>
void build(ll _n, const ArrType &_arr) {
n = _n;
arr.resize(n+1);
st.resize(n*4+4);
lz.resize(n*4+4);
for (ll i=1; i<=n; i++) arr[i] = _arr[i];
_build(1, n, 1);
}
void _build(ll l, ll r, ll rt) {
if (l == r) {
st[rt] = arr[l];
return;
}
_build(l, m, lc);
_build(m + 1, r, rc);
st[rt] = combine(st[lc], st[rc]);
}
void push(ll rt) {
st[lc] = mapping(st[lc], lz[rt]);
lz[lc] = compose(lz[lc], lz[rt]);
st[rc] = mapping(st[rc], lz[rt]);
lz[rc] = compose(lz[rc], lz[rt]);
lz[rt] = {0, -1};
}
void modify(ll ql, ll qr, TagType qx) {
_modify(ql, qr, qx, 1, n, 1);
}
void _modify(ll ql, ll qr, TagType qx, ll l, ll r, ll rt) {
if (ql <= l && r <= qr) {
st[rt] = mapping(st[rt], qx);
lz[rt] = compose(lz[rt], qx);
// cout << l << "--" << r << ":" << qx.add << " " << qx.set << "\n";
return;
}
if (qr < l || r < ql) return;
push(rt);
_modify(ql, qr, qx, l, m, lc);
_modify(ql, qr, qx, m + 1, r, rc);
st[rt] = combine(st[lc], st[rc]);
}
NodeType query(ll ql, ll qr) {
return _query(ql, qr, 1, n, 1);
}
NodeType _query(ll ql, ll qr, ll l, ll r, ll rt) {
if (qr < l || r < ql) return unit();
if (ql <= l && r <= qr) return st[rt];
NodeType ans = unit();
push(rt);
if (ql <= m) ans = combine(ans, _query(ql, qr, l, m, lc));
if (qr > m) ans = combine(ans, _query(ql, qr, m + 1, r, rc));
return ans;
}
#undef m
#undef lc
#undef rc
};
struct node {long long val = 0, sz = 1;};
constexpr inline node combine(node a, node b) {return {a.val+b.val, a.sz+b.sz};}
constexpr inline node unit() {return {0, 0};}
struct tag {long long add = 0, set = -1;};
constexpr node mapping(node a, tag t) {
a.sz += t.add;
if (t.set != -1) a.val = a.sz * t.set;
return a;
}
constexpr tag compose(tag a, tag b) {
a.add += b.add;
if (b.set != -1) return {a.add, b.set};
return a;
}
long long solve1(vector<ll> h, ll n) {
vector<pair<ll, ll>> hh(n);
for (ll i=0; i<n; i++) hh[i] = {h[i], i};
vector<ll> a(n);
ll mx = 0;
for (ll i=0; i<n; i++) {
mx = max(mx, h[i]);
a[i] = mx;
}
ll mx2 = 0;
for (ll i=n-1; i>0; i--) {
mx2 = max(mx2, h[i]);
if (mx2 == mx) break;
a[i] = mx2;
}
sort(hh.begin(), hh.end());
long long ans = 0;
LazySegmentTree<node, combine, unit, tag, mapping, compose> ST;
ST.build(n);
ll r = n;
long long lh = 0;
for (auto [x, j]:hh) {
j++;
while (ST.query(r, r).val >= a[r-1]) {
ans -= lh * (lh - a[r-1]);
r--;
}
node tmp = ST.query(j, r);
ans += x * (tmp.sz * x - tmp.val);
// cout << j << "-" << r << ":" << tmp.sz << " " << tmp.val << " ans: " << ans << "\n";
ST.modify(j, j, {1, -1});
ST.modify(j, r, {0, x});
// cout << j << ":" << ans << "\n";
lh = x;
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<ll> h(n);
for (ll i=0; i<n; i++) cin >> h[i];
vector<ll> a(n);
ll mx = 0;
for (ll i=0; i<n; i++) {
mx = max(mx, h[i]);
a[i] = mx;
}
ll mx2 = 0;
for (ll i=n-1; i>0; i--) {
mx2 = max(mx2, h[i]);
if (mx2 == mx) break;
a[i] = mx2;
}
long long ans = 0;
ans += solve1(h, n);
reverse(h.begin(), h.end());
// cout << "------\n";
ans += solve1(h, n);
reverse(h.begin(), h.end());
for (ll i=0; i<n; i++) {
ans += (h[i] + a[i] - 1) * (a[i] - h[i]) / 2;
// cout << ans << "\n";
}
cout << ans << "\n";
}
/*
8
3 2 4 5 4 1 2 1
12
5 4 4 4 3 3 3 4 4 4 5 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
