#pragma GCC optimize ("Ofast")
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
ll const N = 5e3 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;
ll n, q;
ll a[N], c[N], t[4 * N], w[4 * N], tol[N], tor[N];
void push(ll i, ll tl, ll tr) {
if(w[i] == -1) return;
ll mid = (tl + tr) / 2;
w[i + i] = w[i];
w[i + i + 1] = w[i];
t[i + i] = (mid - tl + 1) * max(0ll, w[i]);
t[i + i + 1] = (tr - mid) * max(0ll, w[i]);
w[i] = -1;
}
void update(ll i, ll tl, ll tr, ll l, ll r, ll val) {
if(tr < l || r < tl)
return;
if(l <= tl && tr <= r) {
t[i] = (tr - tl + 1) * max(0ll, val);
w[i] = val;
return;
}
push(i, tl, tr);
ll mid = (tl + tr) / 2;
update(i + i, tl, mid, l, r, val);
update(i + i + 1, mid + 1, tr, l, r, val);
t[i] = t[i + i] + t[i + i + 1];
}
ll get(ll i, ll tl, ll tr, ll l, ll r) {
if(tr < l || r < tl)
return 0;
if(l <= tl && tr <= r)
return t[i];
push(i, tl, tr);
ll mid = (tl + tr) / 2;
return get(i + i, tl, mid, l, r) + get(i + i + 1, mid + 1, tr, l, r);
}
ll calc(ll l, ll r) {
update(1, 1, n, 1, n, -1);
fr(i, l, r) {
ll x = max(tol[i] + 1, l);
update(1, 1, n, x, i, a[i]);
c[i] += get(1, 1, n, l, i);
}
update(1, 1, n, 1, n, -1);
frb(i, r, l) {
ll x = min(tor[i] - 1, r);
update(1, 1, n, i, x, a[i]);
c[i] += get(1, 1, n, i, r);
c[i] -= a[i];
}
ll ans = INF;
fr(i, l, r) {
chmin(ans, c[i]);
c[i] = 0;
}
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
n = H.size(), q = L.size();
fr(i, 1, n)
a[i] = H[i - 1];
a[0] = INF, a[n + 1] = INF;
stack <ll> st;
st.push(0);
fr(i, 1, n) {
while(a[st.top()] < a[i])
st.pop();
tol[i] = st.top();
st.push(i);
}
while(st.size())
st.pop();
st.push(n + 1);
frb(i, n, 1) {
while(a[st.top()] < a[i])
st.pop();
tor[i] = st.top();
st.push(i);
}
vector <ll> ans;
fr(i, 0, q - 1) {
ans.pb(calc(L[i] + 1, R[i] + 1));
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |