#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1000005 typedef long long lld; int N, C; int L[MAXN], D[MAXN]; int A[MAXN], B[MAXN]; lld X[MAXN], V1[MAXN], V2[MAXN]; int proc(lld d) { lld p = -1e18, q = 1e18, r = -1e18, s = 1e18; lld mn1 = 1e18, mn2 = 1e18; for (int i=1,j=1;i<=N;i++){ while (j <= N && V1[B[j]] > d+V2[A[i]]){ lld v = V2[B[j]]; if (mn1 > v) mn2 = mn1, mn1 = v; else if (mn2 > v) mn2 = v; j++; } if (j == 1 || j == 2 && B[1] == A[i]) continue; int x = A[i], y = B[1] == A[i] ? B[2] : B[1]; lld v = d - D[x] - D[y] - C; q = min(q, X[x]-X[y]+v); r = max(r, X[x]+X[y]-v); v = d - D[x] - C + (mn1 == V2[x] ? mn2 : mn1); p = max(p, X[x]-v); s = min(s, X[x]+v); if (p > q || r > s) return 0; } // Check there is exact station for l, r we have int t = 1; for (int i=1;i<=N;i++){ lld a = max(p + X[i], r - X[i]); lld b = min(q + X[i], s - X[i]); while (t > 1 && X[t-1] >= a) t--; while (t <= N && X[t] < a) t++; if (t <= N && X[t] <= b) return 1; } return 0; } lld find_shortcut(int n, vector<int> l, vector<int> d, int c) { N = n; C = c; int mx1 = 0, mx2 = 0; for (int i=1;i<=N;i++){ L[i] = l[i-1]; D[i] = d[i-1]; X[i] = X[i-1] + L[i-1]; V1[i] = X[i] + D[i]; V2[i] = X[i] - D[i]; if (mx1 < D[i]) mx2 = mx1, mx1 = D[i]; else if (mx2 < D[i]) mx2 = D[i]; } V1[0] = V2[0] = 1e18; for (int i=1;i<=N;i++) A[i] = B[i] = i; sort(A+1, A+N+1, [](const int &a, const int &b){ return V2[a] > V2[b]; }); sort(B+1, B+N+1, [](const int &a, const int &b){ return V1[a] > V1[b]; }); lld s = mx1+mx2, e = 1e16, ans; while (s <= e){ lld m = (s+e)>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } return ans; }

shortcut.cpp: In function 'int proc(lld)':
shortcut.cpp:24:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (j == 1 || j == 2 && B[1] == A[i]) continue;
                              ^
shortcut.cpp: In function 'lld find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:72:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^