#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 750005;
const int MAXT = 2100000;
const int inf = 1e9 + 10;
struct seg{
int lim;
pi tree[MAXT];
void init(vector<int> &v){
for(lim = 1; lim <= v.size(); lim <<= 1);
fill(tree, tree + MAXT, pi(-1e9, 0));
for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
for(int i=lim-1; i; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
}
pi query(int s, int e){
s += lim;
e += lim;
pi ret(-1e9, 0);
while(s < e){
if(s%2 == 1) ret = max(ret, tree[s++]);
if(e%2 == 0) ret = max(ret, tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) ret = max(ret, tree[s]);
return ret;
}
}seg;
struct node{
int s, e, rep; // node range
int lp, rp; // pointers
int h; // height
}tr[MAXN];
int ptr, loc[MAXN], par[MAXN];
lint dp[MAXN], lgo[MAXN], rgo[MAXN];
void make_tree(int s, int e, int v){
int h, m;
tie(h, m) = seg.query(s, e);
loc[m] = v;
tr[v] = {s, e, m, -1, -1, h};
if(s <= m - 1){
ptr++;
tr[v].lp = ptr;
make_tree(s, m-1, tr[v].lp);
}
if(m + 1 <= e){
ptr++;
tr[v].rp = ptr;
make_tree(m+1, e, tr[v].rp);
}
}
lint go_left(int pos, int root){
int L = pos;
lint ret = 1e18;
while(pos != root){
int v = loc[pos];
ret = min(ret, lgo[v] - lgo[tr[loc[root]].lp] + 1ll * tr[v].h * (tr[v].e - L + 1));
if(~tr[v].rp){
ret = min(ret, lgo[v] - lgo[tr[loc[root]].lp] + 1ll * tr[v].h * (tr[v].rep - L + 1) + dp[tr[v].rp]);
}
pos = tr[v].e + 1;
}
// printf("go_left %d -> %d = %lld\n", L, root, ret);
return ret;
}
lint go_right(int pos, int root){
int R = pos;
lint ret = 1e18;
while(pos != root){
int v = loc[pos];
ret = min(ret, rgo[v] - rgo[tr[loc[root]].rp] + 1ll * tr[v].h * (R - tr[v].s + 1));
if(~tr[v].lp){
ret = min(ret, rgo[v] - rgo[tr[loc[root]].rp] + 1ll * tr[v].h * (R - tr[v].rep + 1) + dp[tr[v].lp]);
}
pos = tr[v].s - 1;
}
// printf("go_right %d -> %d = %lld\n", R, root, ret);
return ret;
}
vector<lint> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
int n = H.size();
int q = L.size();
seg.init(H);
make_tree(0, n-1, 0);
for(int i=ptr; i>=0; i--){
dp[i] = 1ll * H[tr[i].rep] * (tr[i].e - tr[i].s + 1);
if(~tr[i].lp){
dp[i] = min(dp[i], dp[tr[i].lp] + 1ll * H[tr[i].rep] * (tr[i].e - tr[i].rep + 1));
}
if(~tr[i].rp){
dp[i] = min(dp[i], dp[tr[i].rp] + 1ll * H[tr[i].rep] * (tr[i].rep - tr[i].s + 1));
}
}
for(int i=0; i<=ptr; i++){
// printf("%d %d %d %d %d %d\n", i, tr[i].lp, tr[i].rp, tr[i].s, tr[i].e, tr[i].rep);
// printf("LGO = %lld, RGO = %lld, DP = %lld\n", lgo[i], rgo[i], dp[i]);
if(~tr[i].lp){
lgo[tr[i].lp] = lgo[i] + 1ll * H[tr[i].rep] * (tr[i].e - i + 1);
rgo[tr[i].lp] = rgo[i];
}
if(~tr[i].rp){
lgo[tr[i].rp] = lgo[i];
rgo[tr[i].rp] = rgo[i] + 1ll * H[tr[i].rep] * (i - tr[i].s + 1);
}
}
vector<lint> ret(q);
for(int i=0; i<q; i++){
pi p = seg.query(L[i], R[i]);
ret[i] = min({1ll * (R[i] - L[i] + 1) * p.first,
go_left(L[i], p.second) + 1ll * (R[i] - p.second + 1) * p.first,
go_right(R[i], p.second) + 1ll * (p.second - L[i] + 1) * p.first});
}
return ret;
}
Compilation message
meetings.cpp: In member function 'void seg::init(std::vector<int>&)':
meetings.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(lim = 1; lim <= v.size(); lim <<= 1);
~~~~^~~~~~~~~~~
meetings.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++) tree[i + lim] = pi(v[i], i);
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16792 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
17004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16792 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
17004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16732 KB |
Output is correct |
| 2 |
Incorrect |
609 ms |
18724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16732 KB |
Output is correct |
| 2 |
Incorrect |
609 ms |
18724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16792 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
17004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
