//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'
int n;
vector<ll> w , h;
ll dp[200000] , inf[200000][2];
set<arr(2)> pt;
void init(){
for(int i = 1 ; i < n ; i++) w[i] += w[i - 1];
for(int i = 0 ; i < n ; i++){
inf[i][1] = (h[i] * h[i]) , inf[i][0] = (h[i] * h[i]) - w[i];
if(i > 0) inf[i][1] += w[i - 1];
}
}
bool jg(ll c , int i , int j){
return (dp[i] - (2 * c * h[i]) <= dp[j] - (2 * c * h[j]));
}
int bsMx(int i){
int l = 0 , r = int(1e6) + 1;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
int inx = (*(--pt.ub({c , int(1e9)})))[1];
if(h[inx] < h[i]) l = c - 1;
else{
if(jg(c , i , inx)) l = c - 1;
else r = c;
}
}
if(r - l - 1 == 1){
int inx = (*(--pt.ub({l + 1 , int(1e9)})))[1];
if(h[inx] < h[i]) return l + 1;
else if(jg(l + r , i , inx)) return l + 1;
}
return l;
}
int bsMn(int i , int r){
int l = -1;
while(r - l - 1 > 1){
int c = (r + l + 1) >> 1;
int inx = (*(--pt.ub({c , int(1e9)})))[1];
if(jg(c , i , inx)) r = c;
else l = c - 1;
}
if(r - l - 1 == 1){
dd[0] = r - 1;
int inx = (*(--pt.ub({r - 1 , int(1e9)})))[1];
if(jg(r - 1 , i , inx)) return r - 1;
}
return r;
}
void addEl(int i){
if(pt.empty()){
pt.insert({0 , i});
return;
}
int r = bsMx(i);
int l = bsMn(i , r + 1);
// cout << i << " " << l << " " << r << "*\n";
if(l > r) return;
auto itr1 = pt.lb({l , -1}) , itr2 = pt.ub({r , int(1e9)});
if(itr1 == itr2){
pt.insert({l , i});
return;
}
vector<arr(2)> dls , adds;
itr2--;
while(true){
dls.pb((*itr1));
if(itr2 == itr1){
adds.pb({r + 1 , (*itr2)[1]});
if((*++itr1)[0] == r + 1) adds.cl();
break;
}
itr1++;
}
pt.insert({l , i});
for(auto &el : dls) pt.erase(el);
for(auto &el : adds) pt.insert(el);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
h.pb(0);
cin >> h.back();
}
for(int i = 0 ; i < n ; i++){
w.pb(0);
cin >> w.back();
}
init();
dp[n - 1] += inf[n - 1][1];
addEl(n - 1);
for(int i = n - 2 ; i >= 0 ; i--){
// for(auto el : pt) cout << el[0] << " " << el[1] << ",,\n";
// cout << "-----\n";
int inx = (*(--pt.ub({h[i] , int(1e9)})))[1];
dp[i] = dp[inx] + inf[i][0] - (2 * h[i] * h[inx]);
if(i > 0) dp[i] += inf[i][1];
// cout << dp[i] << "!!\n";
addEl(i);
}
// cout << jg(0 , 1 , 2) << "::\n";
cout << dp[0];
}
Compilation message
building.cpp: In function 'int bsMn(int, int)':
building.cpp:59:9: error: 'dd' was not declared in this scope; did you mean 'dp'?
59 | dd[0] = r - 1;
| ^~
| dp
