#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;
const int mxn = 1e6 + 5;
int n;
ll c;
ll a[mxn] = {}, b[mxn] = {};
bool check[mxn] = {}, check2[mxn] = {};
pair<ll, ll> st[mxn];
pair<ll, ll> calc12(ll D) {
int sz = 0, nxt1 = 0, nxt2 = 0;
ll rtn1 = -inf, rtn2 = -inf;
st[sz++] = { a[0] + b[0], -a[0] + b[0] };
for (int j = 1; j < n; j++) {
if (check[j]) {
nxt2 = min(nxt2, sz - 1);
while (nxt2 + 1 < sz && c - D + st[nxt2].first - a[j] + b[j] <= rtn2) nxt2++;
if (c - D + st[nxt2].first - a[j] + b[j] > rtn2) {
if (st[nxt2].second + a[j] + b[j] > D) {
while (nxt2 + 1 < sz && st[nxt2 + 1].second + a[j] + b[j] > D) nxt2++;
rtn2 = max(rtn2, c - D + st[nxt2].first - a[j] + b[j]);
}
}
}
if (check2[j]) {
while (nxt1 + 1 < sz && st[nxt1 + 1].second > D - b[j] - a[j]) nxt1++;
while (nxt1 && st[nxt1].second <= D - b[j] - a[j]) nxt1--;
if (st[nxt1].second > D - b[j] - a[j])
rtn1 = max(rtn1, c - D + st[nxt1].first + a[j] + b[j]);
}
if (st[sz - 1].first < a[j] + b[j]) {
while (sz && st[sz - 1].second <= -a[j] + b[j]) sz--;
st[sz++] = { a[j] + b[j], -a[j] + b[j] };
}
}
return{ rtn1, rtn2 };
}
pair<ll, ll> calc34(ll D) {
ll rtn3 = inf, rtn4 = inf;
ll mx = b[0] - a[0];
for (int j = 1; j < n; j++) {
if (mx > D - b[j] - a[j]) {
rtn3 = min(rtn3, D - c - mx + a[j] - b[j]);
rtn4 = min(rtn4, D - c - mx - a[j] - b[j]);
}
mx = max(mx, b[j] - a[j]);
}
return{ rtn3, rtn4 };
}
bool can(ll v[5]) {
ll d[2] = { v[2], v[4] };
ll s[2] = { v[1], v[3] };
if (d[0] > d[1] || s[0] > s[1]) return false;
int dl = 0, dr = 0, sl = n - 1, sr = n - 1; // difference applies on [dl, dr), sum on (sl, sr]
for (int i = 0; i < n; i++) {
dl = max(dl, i + 1);
dr = max(dr, i + 1);
if (dl > sr) return false;
while (dl < n && a[i] - a[dl] > d[1]) dl++;
while (dr < n && a[i] - a[dr] >= d[0]) dr++;
while (sl > 0 && a[i] + a[sl] >= s[0]) sl--;
while (sr > 0 && a[i] + a[sr] > s[1]) sr--;
if (max(dl, sl + 1) <= min(dr - 1, sr))
return true;
}
return false;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> c;
for (int i = 1; i < n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
for (int i = 0; i < n; i++) cin >> b[i];
check[n - 1] = true;
ll mmx = -a[n - 1] + b[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (-a[i] + b[i] > mmx) {
mmx = -a[i] + b[i];
check[i] = true;
}
}
check2[n - 1] = true;
mmx = a[n - 1] + b[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (a[i] + b[i] > mmx) {
mmx = a[i] + b[i];
check2[i] = true;
}
}
ll v[5];
ll lo = 0, hi = 1000000000LL * (n + 2), mid;
pair<ll, ll> p;
while (lo < hi) {
mid = (lo + hi) / 2;
p = calc34(mid);
v[3] = p.first;
v[4] = p.second;
p = calc12(mid);
v[1] = p.first;
v[2] = p.second;
if (can(v)) hi = mid;
else lo = mid + 1;
}
finish(lo);
}
Compilation message
/tmp/ccTpsh9q.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUV4Ngg.o:shortcut.cpp:(.text.startup+0x0): first defined here
/tmp/ccTpsh9q.o: In function `main':
grader.cpp:(.text.startup+0x10d): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
