#include <bits/stdc++.h>
#include "walk.h"
#include "grader.cpp"
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a:b)
#define INF 1e18
#define pb push_back
#define fi first
#define se second
#define sz size()
#define all(a) a.begin(), a.end()
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n=x.sz, m=l.sz, N=0;
// change graph
RE(j,2) {
int x = j ? s : g;
vi nl, nr, ny;
priority_queue<iii> pq;
RE(i,n) pq.push({h[i],2,i});
RE(i,m) {
if(l[i] < x && x < r[i]) {
pq.push({y[i],1,i});
} else {
nl.pb(l[i]);
nr.pb(r[i]);
ny.pb(y[i]);
}
}
int mostL = -1e9, mostR = 1e9;
while(!pq.empty()) {
iii p = pq.top(); pq.pop();
int y, t, i;
tie(y,t,i) = p;
if(t == 2) {
if(i <= x)
mostL = max(mostL, i);
if(i >= x)
mostR = min(mostR, i);
} else if(t == 1) {
nl.pb(l[i]); nr.pb(mostL); ny.pb(y);
nl.pb(mostL); nr.pb(mostR); ny.pb(y);
nl.pb(mostR); nr.pb(r[i]); ny.pb(y);
}
}
l=nl; r=nr; y=ny;
m = l.sz;
}
l.pb(s); r.pb(s); y.pb(0);
l.pb(g); r.pb(g); y.pb(0);
m = l.sz;
ll ans = INF;
map<ii, int> vertexes;
map<int, vi> horVertex;
vector<vii> adj;
auto getVert = [&](int x, int y) {
if(vertexes.count({x,y})) return vertexes[{x,y}];
horVertex[y].pb(x);
return vertexes[{x,y}] = N++;
};
auto connect = [&](ii a, ii b) {
int u = getVert(a.fi, a.se);
int v = getVert(b.fi, b.se);
int d = abs(a.fi-b.fi)+abs(a.se-b.se);
adj[u].pb({v,d});
adj[v].pb({u,d});
};
adj.resize(m*7);
// create vertexes, and vertical edges
{
priority_queue<iii> pq;
multiset<int> st;
RE(i,m) pq.push({r[i],2,i});
RE(i,m) pq.push({l[i],1,i});
RE(i,m) pq.push({r[i],1,i});
RE(i,m) pq.push({l[i],0,i});
while(!pq.empty()) {
iii p = pq.top(); pq.pop();
int cx, t, i;
tie(cx,t,i) = p;
if(t == 2) {
// right
st.insert(y[i]);
} else if(t == 1) {
// connect
getVert(x[cx], y[i]);
auto it = st.lower_bound(y[i]);
if(it != st.begin())
--it, connect({x[cx],y[i]}, {x[cx],*it});
} else {
// left
st.erase(st.find(y[i]));
}
}
}
// create horizontal edges
{
FOR(p,horVertex) sort(all(p.se));
RE(i,m) {
if(l[i] == r[i]) continue;
vi& f = horVertex[y[i]];
auto it=lower_bound(all(f), x[l[i]]);
auto ed=upper_bound(all(f), x[r[i]]);
while(1) {
auto prev = it++;
if(it == ed) break;
connect({*prev, y[i]}, {*it, y[i]});
}
}
}
// dijkstra
{
vll dist; dist.assign(N, INF);
priority_queue<lll> pq;
dist[getVert(x[s],0)] = 0; pq.push({getVert(x[s],0), 0});
while(!pq.empty()) {
lll p = pq.top(); pq.pop();
int u=p.fi; ll d=p.se;
if(dist[u] != d) continue;
FOR(p,adj[u]) {
int v = p.fi;
ll add = p.se;
if(d+add < dist[v]) {
dist[v] = d+add;
pq.push({v,dist[v]});
}
}
}
ans = dist[getVert(x[g],0)];
}
if(ans == INF) ans = -1;
return ans;
}
Compilation message
/tmp/ccHysnv0.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccVfN4gk.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
