| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 814832 |
2023-08-08T10:22:49 Z |
ymm |
Sky Walking (IOI19_walk) |
C++17 |
|
1708 ms |
1048576 KB |
#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 *> q = {s};
Loop (i,0,q.size()) {
node *v = q[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;
q.push_back(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);
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);
for (int j : vec) {
walk[i].lp.a.emplace_back(&walk[j].lp, 2*(pos[walk[i].lpr] - pos[walk[j].lpr]) + abs(walk[i].h - walk[j].h));
walk[j].lp.a.emplace_back(&walk[i].lp, 2*(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);
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);
for (int j : vec) {
walk[i].rp.a.emplace_back(&walk[j].rp, 2*(pos[walk[j].rpl] - pos[walk[i].rpl]) + abs(walk[i].h - walk[j].h));
walk[j].rp.a.emplace_back(&walk[i].rp, 2*(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);
}
spfa(&walk[1].mp);
return walk[0].mp.dis + pos[g] - pos[s];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
15092 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15188 KB |
Output is correct |
| 3 |
Runtime error |
1708 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
88360 KB |
Output is correct |
| 2 |
Correct |
142 ms |
35960 KB |
Output is correct |
| 3 |
Correct |
179 ms |
37140 KB |
Output is correct |
| 4 |
Correct |
232 ms |
43392 KB |
Output is correct |
| 5 |
Correct |
228 ms |
42216 KB |
Output is correct |
| 6 |
Correct |
214 ms |
41008 KB |
Output is correct |
| 7 |
Correct |
112 ms |
32068 KB |
Output is correct |
| 8 |
Correct |
178 ms |
33152 KB |
Output is correct |
| 9 |
Correct |
207 ms |
39848 KB |
Output is correct |
| 10 |
Correct |
114 ms |
33488 KB |
Output is correct |
| 11 |
Incorrect |
15 ms |
17744 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
88360 KB |
Output is correct |
| 2 |
Correct |
142 ms |
35960 KB |
Output is correct |
| 3 |
Correct |
179 ms |
37140 KB |
Output is correct |
| 4 |
Correct |
232 ms |
43392 KB |
Output is correct |
| 5 |
Correct |
228 ms |
42216 KB |
Output is correct |
| 6 |
Correct |
214 ms |
41008 KB |
Output is correct |
| 7 |
Correct |
112 ms |
32068 KB |
Output is correct |
| 8 |
Correct |
178 ms |
33152 KB |
Output is correct |
| 9 |
Correct |
207 ms |
39848 KB |
Output is correct |
| 10 |
Correct |
114 ms |
33488 KB |
Output is correct |
| 11 |
Incorrect |
15 ms |
17744 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 2 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 3 |
Correct |
7 ms |
15188 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
15092 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
