#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<lint, lint> pi; int n, c; lint a[1000005], b[1000005]; struct seg1{ lint mx, smx; int mxf, smxf; void init(){ mx = smx = -1e18; mxf = smxf = -1; } void upd(int x, lint v){ if(v >= mx){ smx = mx, smxf = mxf; mx = v, mxf = x; } else if(v >= smx){ smx = v, smxf = x; } } lint query(int x){ if(mxf != x) return mx; else return smx; } }seg1; struct seg2{ lint mx, smx; int mxf, smxf; void init(){ mx = smx = 1e18; mxf = smxf = -1; } void upd(int x, lint v){ if(v <= mx){ smx = mx, smxf = mxf; mx = v, mxf = x; } else if(v <= smx){ smx = v, smxf = x; } } lint query(int x){ if(mxf != x) return mx; else return smx; } }seg2; vector<pi> v, w; bool trial(lint x){ lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18; seg1.init(); seg2.init(); int p = 0; for(int i=0; i<n; i++){ while(p < n && w[p].first + x < v[i].first){ seg1.upd(w[p].second + 1, a[w[p].second] + b[w[p].second]); seg2.upd(w[p].second + 1, -a[w[p].second] + b[w[p].second]); p++; } lint q1 = seg1.query(v[i].second), q2 = seg2.query(v[i].second); ps = max(ps, q1 - x + c + b[v[i].second] + a[v[i].second]); pe = min(pe, q2 + x - c + b[v[i].second] - a[v[i].second]); ms = max(ms, q1 - x + c - b[v[i].second] + a[v[i].second]); me = min(me, q2 + x - c - b[v[i].second] - a[v[i].second]); } p = 0; for(int i=0; i<n; i++){ while(p < n && max(ps - b[i], b[i] - me) > b[p]) p++; while(p > 0 && max(ps - b[i], b[i] - me) <= b[p-1]) p--; while(p < n && b[p] <= min(pe - b[i], b[i] - ms)) return true; } return false; } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { ::n = n; ::c = c; for(int i=0; i<n; i++){ a[i] = d[i]; if(i >= 1) b[i] = b[i-1] + l[i-1]; } for(int i=0; i<n; i++){ v.push_back(pi(a[i] + b[i], i)); w.push_back(pi(-a[i] + b[i], i)); } sort(v.begin(), v.end()); sort(w.begin(), w.end()); lint s = 0, e = 1e16; while(s != e){ lint m = (s+e)/2; if(trial(m)) e = m; else s = m+1; } return s; }