#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];
pi v[1000005], w[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, a[w[p].second] + b[w[p].second]);
seg2.upd(w[p].second, -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[i] = pi(a[i] + b[i], i);
w[i] = pi(-a[i] + b[i], i);
}
sort(v, v+n);
sort(w, w+n);
lint s = 0, e = 2e15;
while(s != e){
lint m = (s+e)/2;
if(trial(m)) e = m;
else s = m+1;
}
return s;
}
Compilation message
shortcut.cpp:54:12: error: conflicting declaration 'std::vector<std::pair<long long int, long long int> > v'
vector<pi> v, w;
^
shortcut.cpp:9:4: note: previous declaration as 'pi v [1000005]'
pi v[1000005], w[1000005];
^
shortcut.cpp:54:15: error: conflicting declaration 'std::vector<std::pair<long long int, long long int> > w'
vector<pi> v, w;
^
shortcut.cpp:9:16: note: previous declaration as 'pi w [1000005]'
pi v[1000005], w[1000005];
^
