이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "walk.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define fi first
#define se second
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
const int MAXN = 100055;
const int MAXM = 100055;
const int MAXK = 1400055;
struct EVT {
EVT(int type, pii p)
: type(type), p(p) {}
int type;
pii p;
bool operator < (const EVT &t) const {
if(p.fi != t.p.fi) return p.fi < t.p.fi;
return type < t.type;
}
};
vector<int> G[MAXK];
ll dp[MAXK];
map<pii, int> MP;
vector<pii> PV;
int A[MAXN], B[MAXN];
int C[MAXM], D[MAXM], E[MAXM];
int N, M, K, Si, Ei;
ll solve() {
{
vector<pii> OV;
for(int i = N; i--;) OV.eb(-B[i], -(i+1));
for(int i = M; i--;) OV.eb(-E[i], i+1);
sorv(OV);
auto f = [&](int x) {
set<int> PQ;
for(auto &ev : OV) {
int idx = ev.se;
if(idx < 0) {
idx = -idx-1;
PQ.insert(idx);
} else {
idx--;
if(D[idx] <= x) {
auto it = PQ.find(D[idx]);
PV.eb(A[*it], E[idx]);
PV.eb(A[*prev(it)], E[idx]);
} else if(x <= C[idx]) {
auto it = PQ.find(C[idx]);
PV.eb(A[*it], E[idx]);
PV.eb(A[*next(it)], E[idx]);
} else {
auto it = PQ.upper_bound(x-1);
if(PQ.begin() != it) {
it--;
if(C[idx] <= *it && *it <= D[idx])
PV.eb(A[*it], E[idx]);
}
it = PQ.upper_bound(x);
if(PQ.end() != it && C[idx] <= *it && *it <= D[idx])
PV.eb(A[*it], E[idx]);
}
}
}
};
f(Si); f(Ei);
}
if(MAXM*4 < sz(PV)) exit(-1);
{
vector<EVT> EV;
for(int i = M; i--;) {
EV.eb(0, pii(A[C[i]], E[i]));
EV.eb(2, pii(A[D[i]], E[i]));
}
for(auto &v : PV) EV.eb(1, v);
sorv(EV);
multiset<int> PQ;
for(auto &ev : EV) {
if(!ev.type) PQ.insert(ev.p.se);
else if(1 == ev.type) {
auto it = PQ.upper_bound(ev.p.se);
if(PQ.end() != it) PV.eb(ev.p.fi, *it);
if(PQ.begin() != it && *prev(it) == ev.p.se) it--;
if(PQ.begin() != it) PV.eb(ev.p.fi, *prev(it));
} else PQ.erase(PQ.find(ev.p.se));
}
}
if(MAXM*12 < sz(PV)) exit(-1);
PV.eb(A[Si], 0); PV.eb(A[Ei], 0);
for(int i = M; i--;) {
if(C[i] <= Si && Si <= D[i] && E[i] <= B[Si]) PV.eb(A[Si], E[i]);
if(C[i] <= Ei && Ei <= D[i] && E[i] <= B[Ei]) PV.eb(A[Ei], E[i]);
}
sorv(PV); univ(PV);
{
vector<pii> V; K = sz(PV);
for(int i = 0, s = 0, e; i < N; i++, s = e) {
for(e = s; e < K && PV[e].fi == A[i]; e++);
for(int j = s; j < e; j++)
if(PV[j].se <= B[i]) V.eb(PV[j]);
}
swap(PV, V);
}
K = sz(PV);
for(int i = K; i--;) MP[PV[i]] = i;
fill(dp, dp+MAXK, INFLL);
for(int i = 1; i < K; i++)
if(PV[i-1].fi == PV[i].fi) fg(G, i-1, i);
auto cmp = [&](const pii &a, const pii &b) {
if(a.se != b.se) return a.se < b.se;
return a.fi < b.fi;
};
auto _PV = PV;
sort(allv(_PV), cmp);
for(int i = M; i--;) {
int s = int(lower_bound(allv(_PV), pii(A[C[i]], E[i]), cmp) - _PV.begin());
for(int j = s+1; j < K && _PV[j].se == E[i] && _PV[j].fi <= A[D[i]]; j++) fg(G, MP[_PV[j-1]], MP[_PV[j]]);
}
Si = MP[{A[Si], 0}]; Ei = MP[{A[Ei], 0}];
{
priority_queue<pli, vector<pli>, greater<pli>> PQ;
dp[Si] = 0; PQ.emplace(0, Si);
for(ll dst; !PQ.empty();) {
int idx; tie(dst, idx) = PQ.top(); PQ.pop();
if(dp[idx] < dst) continue;
for(int v : G[idx]) {
ll ndst = dst + abs(PV[idx].fi - PV[v].fi) + abs(PV[idx].se - PV[v].se);
if(dp[v] <= ndst) continue;
dp[v] = ndst;
PQ.emplace(ndst, v);
}
}
}
return dp[Ei] >= INFLL ? -1 : dp[Ei];
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
::N = sz(x); ::M = sz(l);
for(int i = 0; i < ::N; i++) {
::A[i] = x[i];
::B[i] = h[i];
}
for(int i = 0; i < ::M; i++) {
::C[i] = l[i];
::D[i] = r[i];
::E[i] = y[i];
}
::Si = s; ::Ei = g;
return solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |