This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Be name khode //
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
const int maxn5 = 75e4 + 5;
const int maxnt = 3e6 + 5;
const int lg = 20;
const ll inf = 1e18;
int n;
vector <ll> ret;
ll a[maxn5];
namespace rmq{
pair <int, int> mx[lg][maxn5];
void build(int n){
for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1))) < n ? mx[i - 1][j + (1 << (i - 1))] : mp(-1, -1));
}
int get_max(int l, int r){
int k = 31 - __builtin_clz(r - l + 1);
return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
}
}
struct cht{
vector <pair<ll, pair<ll, ll>>> av; // {st, {cons, shib}}
cht(){
av.clear();
}
ll inter(pair <ll, ll> a, pair <ll, ll> b){
if(a.se == b.se)
return a.fi > b.fi ? inf : -inf;
//cout << a.fi << ' ' << a.se << ' ' << b.fi << ' ' << b.se << endl;
return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
}
void add(ll cons, ll sh){
ll st = -inf;
while(av.size() && (st = inter(av.back().se, mp(cons, sh))) <= av.back().fi)
av.pop_back();
if(av.empty())
st = -inf;
//cout << "ha? " << cons << ' ' << sh << ' ' << st << ' ' << av.size() << endl;
//cout << (-122) / 46 << endl;
av.pb({st, {cons, sh}});
}
ll get(ll x){
if(av.empty())
return -inf;
int pt = upper_bound(all(av), mp(x, mp(inf, inf))) - av.begin() - 1;
//cout << "we all gor " << pt << ' ' << av[pt].se.fi << ' ' << av[pt].se.se << ' ' << av.size() << endl;
//cout << av.back().fi << ' ' << x << endl;
//cout << av.back().se.fi << ' ' << av.back().se.se << endl;
return av[pt].se.fi + av[pt].se.se * x;
}
};
struct segment{
ll lazy[maxnt];
cht seg[maxnt];
segment(){
memset(lazy, 0, sizeof lazy);
}
void build(int l, int r, int v){
if(r - l == 1){
seg[v].add(0, 0);
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
}
void add_cht(int l, int r, int lq, int rq, pair <ll, ll> val, int v){
if(rq <= l || r <= lq)
return;
//cout << "there's " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val.fi << ' ' << val.se << ' ' << v << ' ' << lazy[v] << endl;
val.fi += lazy[v];
if(lq <= l && r <= rq){
////cout << "baba " << val.fi << ' ' << val.se << endl;
seg[v].add(val.fi, val.se);
return;
}
int mid = (l + r) >> 1;
add_cht(l, mid, lq, rq, val, v * 2);
add_cht(mid, r, lq, rq, val, v * 2 + 1);
}
void add(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq)
return;
//cout << "adding " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << val << ' ' << v << endl;
if(lq <= l && r <= rq){
lazy[v] += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, v * 2);
add(mid, r, lq, rq, val, v * 2 + 1);
}
ll get(int l, int r, int id, int v){
ll ret = (-seg[v].get(id)) + lazy[v];
//cout << "look " << l << ' ' << r << ' ' << v << ' ' << ret << ' ' << lazy[v] << ' ' << id << endl;
if(r - l == 1)
return ret;
int mid = (l + r) >> 1;
if(abs(id) < mid)
ret = min(ret, get(l, mid, id, v * 2) + lazy[v]);
else
ret = min(ret, get(mid, r, id, v * 2 + 1) + lazy[v]);
//cout << "fina " << l << ' ' << r << ' ' << ret << ' ' << lazy[v] << endl;
return ret;
}
} pre, suf;
vector <pair<pair<int, int>, int>> req[maxn5];
void cartesian(int l, int r){
if(r - l == 1){
for(auto [p, id] : req[l])
ret[id] = a[l];
pre.add(0, n, l, l + 1, a[l], 1);
suf.add(0, n, l, l + 1, a[l], 1);
return;
}
int mx = rmq::get_max(l, r - 1);
if(l < mx)
cartesian(l, mx);
if(mx + 1 < r)
cartesian(mx + 1, r);
//cout << "in " << l << ' ' << r << ' ' << mx << endl;
for(auto [p, id] : req[mx]){
int lq = p.fi, rq = p.se;
ret[id] = (rq - lq + 1) * a[mx];
//cout << ret[id] << endl;
if(lq < mx)
ret[id] = min(ret[id], suf.get(0, n, lq, 1) + (rq - mx + 1) * a[mx]);
//cout << ret[id] << endl;
if(rq > mx)
ret[id] = min(ret[id], pre.get(0, n, -rq, 1) + (mx - lq + 1) * a[mx]);
//cout << ret[id] << endl;
}
ll keeppre = (l < mx ? pre.get(0, n, -(mx - 1), 1) : 0);
ll keepsuf = (mx + 1 < r ? suf.get(0, n, mx + 1, 1) : 0);
//cout << "in " << l << ' ' << r << ' ' << mx << ' ' << keepsuf << ' ' << keeppre << endl;
pre.add(0, n, mx, r, (mx - l + 1) * a[mx], 1);
suf.add(0, n, l, mx + 1, (r - mx) * a[mx], 1);
pre.add_cht(0, n, mx, r, mp(-(keeppre + (1 - mx) * a[mx]), a[mx]), 1);
//cout << "all here " << endl;
suf.add_cht(0, n, l, mx + 1, mp(-(keepsuf + (1 + mx) * a[mx]), a[mx]), 1);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
std::vector<int> r) {
n = h.size();
for(int i = 0; i < n; i++)
a[i] = h[i];
int q = l.size();
ret.resize(q);
for(int i = 0; i < n; i++)
rmq::mx[0][i] = mp(h[i], i);
rmq::build(n);
for(int i = 0; i < q; i++){
int mx = rmq::get_max(l[i], r[i]);
req[mx].pb({{l[i], r[i]}, i});
}
pre.build(0, n, 1);
suf.build(0, n, 1);
cartesian(0, n);
return ret;
}
# | 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... |