#include "shortcut.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
const int mxn = 1'000'000;
const ll INF = 10'000'000'000'000'000LL;
vll x(1+mxn);
vll y(1+mxn);
long long find_shortcut(int n, vector<int> l_, vector<int> d_, int c_)
{
x[1] = 0;
for(int i = 2; i <= n; i++) x[i] = x[i-1] + l_[i-2];
for(int i = 1; i <= n; i++) y[i] = d_[i-1];
ll l = c_; //shortcut length
int* ord = new int[1+n];
for(int i = 1; i <= n; i++) ord[i] = i;
sort(ord+1, ord+n+1, [] (int u, int v)
{
return y[u] - x[u] > y[v] - x[v];
});
// cerr << "\n\n\n";
// for(int i = 1; i <= n; i++) cerr << i << " : " << x[i] << ' ' << y[i] << ' ' << y[i] - x[i] << '\n';
//
// cerr << "ord = ";
// for(int oi = 1; oi <= n; oi++) cerr << ord[oi] << ' ';
// cerr << '\n';
// cerr << "\n\n\n";
pair<ll, int> xpy_max[1+n], xpy_max2[1+n];
xpy_max[0] = xpy_max2[0] = {-INF, 0};
// xpy_max[1] = {x[ord[1]] + y[ord[1]], ord[1]};
// xpy_max2[1] = {-INF, 0};
// cerr << "COMPUTING MAX\n";
for(int i = 1; i <= n; i++)
{
xpy_max[i] = xpy_max[i-1];
xpy_max2[i] = xpy_max2[i-1];
pair<ll, int> nw = {x[ord[i]] + y[ord[i]], ord[i]};
if(nw <= xpy_max2[i]) ;
else if(nw <= xpy_max[i]) xpy_max2[i] = nw;
else
{
xpy_max2[i] = xpy_max[i];
xpy_max[i] = nw;
}
// cerr << "element = " << ord[i] << " : ";
// cerr << xpy_max[i].first << "|" << xpy_max[i].second << " , " << xpy_max2[i].first << "|" << xpy_max2[i].second << '\n';
}
// cerr << "\n\n\n\n";
// cerr << "COMPUTING MIN\n";
pair<ll, int> xdy_min[1+n], xdy_min2[1+n];
xdy_min[0] = xdy_min2[0] = {INF, 0};
for(int i = 1; i <= n; i++)
{
xdy_min[i] = xdy_min[i-1];
xdy_min2[i] = xdy_min2[i-1];
pair<ll, int> nw = {x[ord[i]] - y[ord[i]], ord[i]};
if(nw >= xdy_min2[i]);
else if(nw >= xdy_min[i]) xdy_min2[i] = nw;
else
{
xdy_min2[i] = xdy_min[i];
xdy_min[i] = nw;
}
// cerr << "element = " << ord[i] << " : ";
// cerr << xdy_min[i].first << "|" << xdy_min[i].second << " , " << xdy_min2[i].first << "|" << xdy_min2[i].second << '\n';
}
sort(ord+1, ord+n+1, [] (int u, int v)
{
return y[u] - x[u] > y[v] - x[v];
});
vi I(n);
for(int i = 0; i < n; i++) I[i] = i+1;
sort(I.begin(), I.end(), [] (int u, int v)
{
return x[u] + y[u] < x[v] + y[v];
});
ll lo = 1;
// ll hi = (1'000'000'000'000'000'000LL);
ll hi = 1'000'000'000LL * ll(n+2);
while(lo != hi)
{
ll k = (lo+hi)/2;
// cerr << "\n\n\n";
// cerr << "k = " << k << '\n';
ll sum_lo = -INF;
ll sum_hi = INF;
ll diff_lo = -INF;
ll diff_hi = INF;
int i_ind = 0;
for(int q = 0; q < n; q++)
{
int j = I[q];
while(i_ind + 1 <= n && y[ord[i_ind + 1]] - x[ord[i_ind + 1]] > k - (x[j] + y[j]))
{
int i = ord[i_ind+1];
if(!(y[i] - x[i] > k - (x[j] + y[j]))) break;
i_ind++;
assert(i < j);
}
ll xpy_maxval = (xpy_max[i_ind].second != j ? xpy_max[i_ind].first : xpy_max2[i_ind].first);
ll xdy_minval = (xdy_min[i_ind].second != j ? xdy_min[i_ind].first : xdy_min2[i_ind].first);
sum_lo = max(sum_lo, xpy_maxval + x[j] + y[j] + l - k);
sum_hi = min(sum_hi, xdy_minval + x[j] - y[j] + k - l);
diff_hi = min(diff_hi, -(xpy_maxval) + x[j] - y[j] + k - l);
diff_lo = max(diff_lo, -(xdy_minval) + x[j] + y[j] + l - k);
}
// cerr << sum_lo << ' ' << sum_hi << ' ' << diff_lo << ' ' << diff_hi << '\n';
bool works = 0;
for(int i = 1; i <= n; i++)
{
for(int j = i+1; j <= n; j++)
{
if(sum_lo <= x[i] + x[j] && x[i] + x[j] <= sum_hi)
{
if(diff_lo <= x[j] - x[i] && x[j] - x[i] <= diff_hi)
{
works = 1;
}
}
// cerr << "val = " << x[i] + x[j] << ' ' << x[j] - x[i] << '\n';
}
}
// cerr << "works = " << works << '\n';
// cerr << lo << ' ' << hi << " -> ";
if(works) hi = k;
else lo = k+1;
// cerr << lo << ' ' << hi << '\n';
}
return lo;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:148:17: error: 'assert' was not declared in this scope
148 | assert(i < j);
| ^~~~~~
shortcut.cpp:5:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
4 | #include <iostream>
+++ |+#include <cassert>
5 | using namespace std;
