#include "walk.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
struct node {
vector<pair<node *, ll>> a;
bool vis;
ll dis;
};
struct {
node lp, mp, rp;
int lpr, mpl, mpr, rpl;
int l, r, h;
} walk[N];
namespace seg {
int mx[N*4];
int t[N*4];
int sz;
void get(int l, int r, int h, vector<int> &ans, int i, int b, int e) {
if (r <= b || e <= l || mx[i] < h || t[i] == -2)
return;
if (l <= b && e <= r && t[i] != -1) {
if (ans.empty() || ans.back() != t[i])
ans.push_back(t[i]);
return;
}
if (t[i] != -1)
t[2*i+1] = t[2*i+2] = t[i];
get(l, r, h, ans, 2*i+1, b, (b+e)/2);
get(l, r, h, ans, 2*i+2, (b+e)/2, e);
}
vector<int> get(int l, int r, int h) {
vector<int> ans;
get(l, r, h, ans, 0, 0, sz);
return ans;
}
void up(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r) {
t[i] = x;
return;
}
if (r <= b || e <= l)
return;
if (t[i] != -1)
t[2*i+1] = t[2*i+2] = t[i];
up(l, r, x, 2*i+1, b, (b+e)/2);
up(l, r, x, 2*i+2, (b+e)/2, e);
t[i] = t[2*i+1] == t[2*i+2]? t[2*i+1]: -1;
}
void up(int l, int r, int x) { up(l, r, x, 0, 0, sz); }
int lrmost(int l, int r, bool d, int h, int i, int b, int e) {
if (mx[i] < h || r <= b || e <= l)
return -1;
if (e-b == 1)
return b;
int x;
if ((x = lrmost(l, r, d, h, 2*i+1+ d, d? (b+e)/2: b, d? e: (b+e)/2)) != -1)
return x;
if ((x = lrmost(l, r, d, h, 2*i+1+!d, d? b: (b+e)/2, d? (b+e)/2: e)) != -1)
return x;
return -1;
}
int leftmost(int l, int r, int h) { return lrmost(l, r, 0, h, 0, 0, sz); }
int rightmost(int l, int r, int h) { return lrmost(l, r, 1, h, 0, 0, sz); }
void init(const vector<int> &vec, int i, int b, int e) {
t[i] = -2;
if (e-b == 1) {
mx[i] = vec[b];
return;
}
init(vec, 2*i+1, b, (b+e)/2);
init(vec, 2*i+2, (b+e)/2, e);
mx[i] = max(mx[2*i+1], mx[2*i+2]);
}
void init(const vector<int> &vec) {
sz = vec.size();
init(vec, 0, 0, sz);
}
}
pii get_walk(node *v)
{
long vi = (long)(void *)v;
long wi = (long)(void *)walk;
long x = (vi - wi)/sizeof(*walk);
long y = (vi - wi)%sizeof(*walk);
y /= sizeof(node);
return {x, y};
}
void spfa(node *s)
{
s->dis = 0;
s->vis = 1;
vector<node *> q1 = {s}, q2;
for (int i = 0;; ++i) {
if (i == q1.size()) {
if (q2.empty())
break;
q1.clear();
q1.swap(q2);
i = 0;
}
node *v = q1[i];
v->vis = 0;
for (auto [u, w] : v->a) {
if (v->dis + w < u->dis) {
u->dis = v->dis + w;
if (!u->vis) {
u->vis = 1;
q2.push_back(u);
}
}
}
}
}
void dij(node *s)
{
s->dis = 0;
set<pair<ll, node *>> S;
S.insert({0, s});
while (S.size()) {
auto [d, v] = *S.begin();
S.erase(S.begin());
for (auto [u, w] : v->a) {
if (d + w < u->dis) {
S.erase({u->dis, u});
u->dis = d+w;
S.insert({u->dis, u});
}
}
}
}
long long min_distance(std::vector<int> pos, std::vector<int> height, std::vector<int> l, std::vector<int> r, std::vector<int> h, int s, int g) {
if (s > g)
swap(s, g);
vector<tuple<int,int,int>> w;
Loop (i,0,h.size())
w.emplace_back(h[i], l[i], r[i]);
w.emplace_back(0, s, s);
w.emplace_back(0, g, g);
sort(w.begin(), w.end());
seg::init(height);
int cnt[3] = {};
Loop (i,0,w.size()) {
auto [h, l, r] = w[i];
walk[i].l = l;
walk[i].r = r;
walk[i].h = h;
bool hl = 0, hm = 0, hr = 0;
if (l < s) {
hl = 1;
walk[i].lpr = seg::rightmost(l, s, h);
vector<int> vec = seg::get(l, s, h);
assert(vec.size() <= cnt[0]);
cnt[0] -= max((int)vec.size() - 2, 0);
cnt[0] += 1;
for (int j : vec) {
walk[i].lp.a.emplace_back(&walk[j].lp, 2ll*(pos[walk[i].lpr] - pos[walk[j].lpr]) + abs(walk[i].h - walk[j].h));
walk[j].lp.a.emplace_back(&walk[i].lp, 2ll*(pos[walk[j].lpr] - pos[walk[i].lpr]) + abs(walk[i].h - walk[j].h));
}
}
if (l <= g || s <= r) {
int ls = max(l, s);
int rs = min(r, g)+1;
walk[i].mpl = seg::leftmost(ls, rs, h);
walk[i].mpr = seg::rightmost(ls, rs, h);
vector<int> vec = seg::get(ls, rs, h);
assert(vec.size() <= cnt[1]);
cnt[1] -= max((int)vec.size() - 2, 0);
cnt[1] += 1;
hm = vec.size();
for (int j : vec) {
walk[i].mp.a.emplace_back(&walk[j].mp, abs(walk[i].h - walk[j].h));
walk[j].mp.a.emplace_back(&walk[i].mp, abs(walk[i].h - walk[j].h));
}
}
if (g < r) {
hr = 1;
walk[i].rpl = seg::leftmost(g+1, r+1, h);
vector<int> vec = seg::get(g+1, r+1, h);
assert(vec.size() <= cnt[2]);
cnt[2] -= max((int)vec.size() - 2, 0);
cnt[2] += 1;
for (int j : vec) {
walk[i].rp.a.emplace_back(&walk[j].rp, 2ll*(pos[walk[j].rpl] - pos[walk[i].rpl]) + abs(walk[i].h - walk[j].h));
walk[j].rp.a.emplace_back(&walk[i].rp, 2ll*(pos[walk[i].rpl] - pos[walk[j].rpl]) + abs(walk[i].h - walk[j].h));
}
}
if (hl && hm) {
walk[i].lp.a.emplace_back(&walk[i].mp, 2*(pos[walk[i].mpl] - pos[s]));
walk[i].mp.a.emplace_back(&walk[i].lp, 2*(pos[s] - pos[walk[i].lpr]));
}
if (hl && hr && !hm) {
walk[i].lp.a.emplace_back(&walk[i].rp, 2*(pos[walk[i].rpl] - pos[s]));
walk[i].rp.a.emplace_back(&walk[i].lp, 2*(pos[s] - pos[walk[i].lpr]));
}
if (hm && hr) {
walk[i].mp.a.emplace_back(&walk[i].rp, 2*(pos[walk[i].rpl] - pos[walk[i].mpr]));
walk[i].rp.a.emplace_back(&walk[i].mp, 0);
}
walk[i].lp.dis = walk[i].mp.dis = walk[i].rp.dis = 1e18;
seg::up(l, r+1, i);
}
dij(&walk[1].mp);
if (walk[0].mp.dis >= (ll)1e18)
return -1;
return walk[0].mp.dis + pos[g] - pos[s];
}
Compilation message
walk.cpp: In function 'void spfa(node*)':
walk.cpp:110:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | if (i == q1.size()) {
| ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from walk.cpp:2:
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:171:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
171 | assert(vec.size() <= cnt[0]);
| ~~~~~~~~~~~^~~~~~~~~
walk.cpp:185:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
185 | assert(vec.size() <= cnt[1]);
| ~~~~~~~~~~~^~~~~~~~~
walk.cpp:198:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
198 | assert(vec.size() <= cnt[2]);
| ~~~~~~~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15184 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15092 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15184 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 5 |
Correct |
7 ms |
15120 KB |
Output is correct |
| 6 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 7 |
Runtime error |
20 ms |
30540 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
15176 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 3 |
Runtime error |
59 ms |
39596 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
22720 KB |
Output is correct |
| 2 |
Runtime error |
52 ms |
39240 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
22720 KB |
Output is correct |
| 2 |
Runtime error |
52 ms |
39240 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
15184 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15092 KB |
Output is correct |
| 3 |
Correct |
8 ms |
15184 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 5 |
Correct |
7 ms |
15120 KB |
Output is correct |
| 6 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 7 |
Runtime error |
20 ms |
30540 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
