//Just some random thing in my mind
#include <bits/stdc++.h>
using namespace std;
const long long inf = 4e18;
struct line{
long long a, b, p;
line(long long a = 0, long long b = 0, long long p = 0) : a(a), b(b), p(p) {}
long long eval(long long x){ return a * x + b; }
bool operator < (const long long& o) const { return p < o; }
friend bool operator < (const line& d1, const line& d2){
return make_pair(d1.a, d1.b) > make_pair(d2.a, d2.b);
}
};
long long divi(long long a, long long b){
return a / b - ((a % b) != 0 && (a ^ b) < 0);
}
void isect(line& d1, const line& d2){
if(d1.a == d2.a) d1.p = (d1.b < d2.b ? inf : -inf);
else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}
struct convex_hull_trick{
deque<line> v;
convex_hull_trick() : v() {}
void add(long long a, long long b){
line d(a, b, inf);
if(!v.empty()) isect(v.back(), d);
while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
v.pop_back();
isect(v.back(), d);
}
v.push_back(d);
}
// long long query(long long x){
// int id = lower_bound(v.begin(), v.end(), x) - v.begin();
// return v[id].eval(x);
// }
long long query(long long x){
while((int)v.size() > 1 && v[0].eval(x) >= v[1].eval(x)) v.pop_front();
return v[0].eval(x);
}
};
template<typename T>
void merge_sort(vector<T>& a, const vector<T>& b){
vector<T> c;
int i = 0, j = 0;
while(i < (int)a.size() || j < (int)b.size()){
if(i == (int)a.size()) c.emplace_back(b[j++]);
else if(j == (int)b.size()) c.emplace_back(a[i++]);
else if(a[i] < b[j]) c.emplace_back(a[i++]);
else c.emplace_back(b[j++]);
}
swap(a, c);
}
const int MAX = 1e5 + 5;
int N, timerNodes, ln[MAX * 2], rn[MAX * 2];
long long dp[MAX], h[MAX], w[MAX];
vector<line> lines[MAX * 2];
vector<pair<int, int>> queries[MAX * 2];
int build(int l, int r){
if(l == r) {
++timerNodes;
queries[timerNodes].emplace_back(-2 * h[l], l);
return timerNodes;
}
int mid = l + r >> 1, cur = ++timerNodes;
ln[cur]= build(l, mid);
rn[cur] = build(mid + 1, r);
queries[cur]= queries[ln[cur]];
merge_sort(queries[cur], queries[rn[cur]]);
return cur;
}
void solve(int l, int r, int cur){
if(l == r) {
lines[cur].emplace_back(h[l], h[l] * h[l] + dp[l] - w[l]);
return;
}
int mid = l + r >> 1;
solve(l, mid, ln[cur]);
convex_hull_trick cht;
for(auto d : lines[ln[cur]]) cht.add(d.a, d.b);
for(auto [slope, i] : queries[rn[cur]]){
dp[i] = min(dp[i], cht.query(slope) + w[i - 1] + h[i] * h[i]);
}
solve(mid + 1, r, rn[cur]);
lines[cur] = lines[ln[cur]];
merge_sort(lines[cur], lines[rn[cur]]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
cin >> N;
for(int i = 1; i <= N; ++i) cin >> h[i];
for(int i = 1; i <= N; ++i) cin >> w[i], w[i] += w[i - 1];
for(int i = 2; i <= N; ++i) dp[i] = inf;
int root = build(1, N);
solve(1, N, root);
for(int i = 1; i <= N; ++i){
cout << dp[i] << ' ';
}
cout << '\n';
cout << dp[N] << '\n';
return 0;
}
Compilation message
building.cpp: In function 'int build(int, int)':
building.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = l + r >> 1, cur = ++timerNodes;
| ~~^~~
building.cpp: In function 'void solve(int, int, int)':
building.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = l + r >> 1;
| ~~^~~
building.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
98 | for(auto [slope, i] : queries[rn[cur]]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
89520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
