#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 75e4+5;
const int MAXH = 1e9;
const int MAXB = 20;
typedef long long ll;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
vector<pil> edges[MAXN]; // node, cost (right inclusive, left exclusive)
vector<ll> ans;
int height[MAXN];
int qleft[MAXN];
int qright[MAXN];
pil line[MAXN];
ll lpos[MAXN];
ll right_cost[MAXN];
int par[MAXN][MAXB]; // 60 mb
int mx[MAXN][MAXB]; // also need this thing
int n, q;
bool less(int i, int j) {
return pii(height[i], i) < pii(height[j], j);
}
bool more(int i, int j) {
return pii(height[i], i) > pii(height[j], j);
}
ll intersect(int i, int j) {
assert(line[j].first > line[i].first);
return (line[i].second-line[j].second+line[j].first-line[i].first-1)/(line[j].first-line[i].first);
}
bool below(int i, int j) {
if (j == 0) return 0;
assert(line[j].first > line[i].first);
ll cmp_pos = intersect(i, j);
return cmp_pos <= lpos[j];
}
void dfs(int cur, int p=-1) { // slope = rightval, intercept = sum of going right + internal
if (cur > 0) { // where does the line fit in
for (int b = MAXB-1; b >= 0; b--) { // number of line parents to go through
if (below(cur, par[p][b])) p = par[p][b];
}
if (below(cur, p)) p = par[p][0];
assert(!below(cur, p));
par[cur][0] = p;
if (p == 0) lpos[cur] = 0;
else lpos[cur] = intersect(cur, p);
for (int b = 1; b < MAXB; b++) par[cur][b] = par[par[cur][b-1]][b-1];
}
for (pil e: edges[cur]) {
int nxt = e.first;
right_cost[nxt] = right_cost[cur]+(ll)(nxt-cur)*height[nxt];
line[nxt] = pil(height[nxt], right_cost[cur]+e.second-(ll)height[nxt]*nxt);
dfs(nxt, cur);
}
// cerr << cur << ' ' << par[cur][0] << endl;
}
int get_mx(int l, int r) {
int b = (31-__builtin_clz(r-l+1));
if (more(mx[l][b], mx[r-(1<<b)+1][b])) return mx[l][b];
return mx[r-(1<<b)+1][b];
}
ll query(int i, int x) {
return (ll)line[i].first*x+line[i].second;
}
ll make_ans(int i, int j) {
int div = get_mx(i, j);
if (div == j) return (ll)MAXH*MAXN;
ll add = (div-i+1)*height[div]-right_cost[div];
int cur = j;
for (int b = MAXB-1; b >= 0; b--) {
if (par[cur][b] > div && j < lpos[par[cur][b]]) cur = par[cur][b];
}
if (par[cur][0] > div && j < lpos[par[cur][0]]) cur = par[cur][0];
assert(par[cur][0] <= div || j >= lpos[par[cur][0]]);
ll res = add+query(cur, j);
// cerr << res << "\n";
return res;
}
void solve() {
for (int i = 0; i < n; i++) edges[i].clear();
// CLEAR ALL VARIABLES
for (int b = 0; b < MAXB; b++) {
for (int i = 0; i < n; i++) {
if (b == 0) {
mx[i][b] = i;
continue;
}
if (i+(1<<b) > n) continue;
else if (more(mx[i][b-1], mx[i+(1<<(b-1))][b-1])) mx[i][b] = mx[i][b-1];
else mx[i][b] = mx[i+(1<<(b-1))][b-1];
}
}
vector<int> stck;
stck.push_back(0);
for (int i = 1; i < n; i++) {
ll running = 0;
int prv = i;
while (more(i, stck.back())) {
if (prv == i) {
prv = stck.back();
running = height[i];
}
else {
running = min(running+height[prv]*(prv-stck.back()),
edges[stck.back()].back().second+(i-prv-1)*height[prv]+height[i]);
prv = stck.back();
}
stck.pop_back();
}
if (prv == i) running = height[i];
else running = min(running+height[prv]*(prv-stck.back()),
edges[stck.back()].back().second+(i-prv-1)*height[prv]+height[i]);
edges[stck.back()].push_back(pil(i, running));
stck.push_back(i);
}
dfs(0);
for (int i = 0; i < q; i++) {
ans[i] = min(ans[i], make_ans(qleft[i], qright[i]));
}
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
q = l.size();
n = h.size();
ans = vector<ll>(q);
fill(ans.begin(), ans.end(), (ll)MAXN*MAXH);
height[0] = MAXH+1;
for (int i = 0; i < n; i++) height[i+1] = h[i];
for (int i = 0; i < q; i++) {
qleft[i] = l[i]+1;
qright[i] = r[i]+1;
}
n++;
solve();
for (int i = 1; i < (n+1)/2; i++) {
swap(height[i], height[n-i]);
}
for (int i = 0; i < q; i++) {
int tmp = qleft[i];
qleft[i] = n-qright[i];
qright[i] = n-tmp;
}
solve();
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
17876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
