#include "walk.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Seg{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> tree[200200];
int sz;
void init(int n){sz = n;}
void update(int x, ll val, int e){
x += sz;
for (;x;x>>=1) tree[x].emplace(val, e);
}
ll query(int l, int r, int s){
++r;
ll ret = INF;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1){
while(!tree[l].empty() && tree[l].top().second < s) tree[l].pop();
if (!tree[l].empty()) ret = min(ret, tree[l].top().first);
l++;
}
if (r&1){
--r;
while(!tree[r].empty() && tree[r].top().second < s) tree[r].pop();
if (!tree[r].empty()) ret = min(ret, tree[r].top().first);
}
}
return ret;
}
}tree1, tree2;
struct Line{
int l, r, y, i;
Line(){}
Line(int _l, int _r, int _y, int _i): l(_l), r(_r), y(_y), i(_i) {}
bool operator < (const Line &L) const{
return tie(l, y) < tie(L.l, L.y);
}
}E[100100];
ll D[100100];
ll myabs(ll x){return x<0?-x:x;}
ll dist(ll x1, ll y1, ll x2, ll y2){return myabs(x1-x2) + myabs(y1-y2);}
vector<int> cy;
int getidx(int y){return lower_bound(cy.begin(), cy.end(), y) - cy.begin();}
long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
int n = x.size(), m = l.size();
if (n==1) return 0;
for (int i=0;i<m;i++) E[i] = Line(x[l[i]], x[r[i]], y[i], i);
sort(E, E+m);
cy = y;
cy.push_back(0);
sort(cy.begin(), cy.end());
cy.erase(unique(cy.begin(), cy.end()), cy.end());
tree1.init(m+1);
tree2.init(m+1);
tree1.update(0, dist(0, 0, 1e9, 1e9), 0);
fill(D, D+m, INF);
//printf("ok\n");
for (int i=0;i<m;){
int j = i;
for (;j<m;j++) if (E[i].l!=E[j].l) break;
for (int k=i;k<j;k++){
D[k] = min(D[k], tree1.query(0, getidx(E[k].y), E[k].l) - dist(E[k].l, E[k].y, 1e9, 1e9));
}
for (int k=j-1;k>=i;k--){
D[k] = min(D[k], tree2.query(getidx(E[k].y)+1, m, E[k].l) - dist(E[k].l, E[k].y, 1e9, 0));
}
for (int k=i;k<j;k++){
tree1.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 1e9), E[k].r);
tree2.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 0), E[k].r);
}
i = j;
}
//for (int i=0;i<m;i++) printf(" %d %d %d -> %lld\n", E[i].l, E[i].r, E[i].y, D[i]);
ll ans = INF;
for (int i=0;i<m;i++) if (E[i].r==x[g]) ans = min(ans, D[i] + dist(E[i].l, E[i].y, x[g], 0));
return ans>=INF/2?-1:ans;
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:57:7: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'std::vector<int>')
57 | cy = y;
| ^
In file included from /usr/include/c++/10/vector:72,
from walk.h:4,
from walk.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
198 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note: no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
199 | operator=(const vector<_Tp, _Alloc>& __x)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
from walk.h:4,
from walk.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
730 | operator=(initializer_list<value_type> __l)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
730 | operator=(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
