#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif
const int N = 1 << 20;
const ll INF = 1e18;
struct Data{
ll a, b;
Data() : a(-INF), b(INF){}
Data(ll a, ll b) : a(a), b(b){}
};
inline void merge(Data & X, const Data & Y){
X.a = max(X.a, Y.a);
X.b = min(X.b,Y.b);
}
Data data[N];
void init(){
for(int i = 0; i < N; i++) data[i] = Data();
}
inline void add(int i, Data d){
i++;
for(; i < N; i += (i & (-i))){
merge(data[i], d);
}
}
Data get(int i){
i++;
Data ret;
for(; i; i -=(i & (-i))) merge(ret, data[i]);
return ret;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
vector<ll> p(n);
for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
vector<int> perm1(n), perm2(n);
vector<int> where(n);
iota(all(perm1), 0);
iota(all(perm2), 0);
sort(all(perm1), [&](int i, int j){return d[i] - p[i] > d[j] - p[j];});
sort(all(perm2), [&](int i, int j){return d[i] + p[i] < d[j] + p[j];});
for(int i = 0; i < n; i++) where[perm1[i]] = i;
ll lo = 0, hi = 1000000000LL * 10000000LL;
vector<int> position(n);
while(lo < hi){
ll D = (lo + hi) / 2;
Data d1, d2;
int cur = 0; // < 0
for(int i : perm2){
while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++;
position[i] = cur;
}
init();
for(int j = 0; j < n; j++){
Data temp = get(position[j] - 1);
d1.a = max(d1.a, temp.a + d[j] + c - p[j] - D);
d1.b = min(d1.b, temp.b - d[j] - c - p[j] + D);
d2.a = max(d2.a, temp.a + p[j] - D + d[j] + c);
d2.b = min(d2.b, temp.b + p[j] + D - d[j] - c);
add(where[j], Data(p[j] + d[j], p[j] - d[j]));
}
ll L1 = d1.a, R1 = d1.b;
ll L2 = d2.a, R2 = d2.b;
if(L1 > R1 || L2 > R2){
lo = D + 1;
continue;
}
// some u, v with p[u] - p[v] in [L1, R1] and p[u] + p[v] in [L2, R2]
bool ok = false;
for(int v = 1; v < n; v++){
ll L = max(p[v] + L1, L2 - p[v]);
ll R = min(p[v] + R1, R2 - p[v]);
// in L, R?
int u = upper_bound(all(p), L - 1) - p.begin(); // first >= L
if(u >= v) continue;
if(p[u] > R) continue;
ok = true;
break;
}
if(ok) hi = D;
else lo = D + 1;
}
return lo;
}
Compilation message
shortcut.cpp: In function 'void init()':
shortcut.cpp:30:32: error: reference to 'data' is ambiguous
30 | for(int i = 0; i < N; i++) data[i] = Data();
| ^~~~
In file included from /usr/include/c++/10/vector:69,
from shortcut.h:2,
from shortcut.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
319 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
310 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
300 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
290 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
shortcut.cpp:28:6: note: 'Data data [1048576]'
28 | Data data[N];
| ^~~~
shortcut.cpp: In function 'void add(int, Data)':
shortcut.cpp:36:15: error: reference to 'data' is ambiguous
36 | merge(data[i], d);
| ^~~~
In file included from /usr/include/c++/10/vector:69,
from shortcut.h:2,
from shortcut.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
319 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
310 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
300 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
290 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
shortcut.cpp:28:6: note: 'Data data [1048576]'
28 | Data data[N];
| ^~~~
shortcut.cpp: In function 'Data get(int)':
shortcut.cpp:43:41: error: reference to 'data' is ambiguous
43 | for(; i; i -=(i & (-i))) merge(ret, data[i]);
| ^~~~
In file included from /usr/include/c++/10/vector:69,
from shortcut.h:2,
from shortcut.cpp:1:
/usr/include/c++/10/bits/range_access.h:319:5: note: candidates are: 'template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)'
319 | data(initializer_list<_Tp> __il) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:310:5: note: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])'
310 | data(_Tp (&__array)[_Nm]) noexcept
| ^~~~
/usr/include/c++/10/bits/range_access.h:300:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)'
300 | data(const _Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
/usr/include/c++/10/bits/range_access.h:290:5: note: 'template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)'
290 | data(_Container& __cont) noexcept(noexcept(__cont.data()))
| ^~~~
shortcut.cpp:28:6: note: 'Data data [1048576]'
28 | Data data[N];
| ^~~~
