답안 #1015406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015406	2024-07-06T10:18:21 Z	MilosMilutinovic	Sky Walking (IOI19_walk)	C++14	100 / 100	2150 ms	218640 KB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int f) {
  int n = (int) x.size();
  int m = (int) y.size();
  const int L = 20;
  vector<vector<int>> mx(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    mx[i][0] = h[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }
  }
  vector<int> logs(n + 1);
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  auto Query = [&](int L, int R) {
    int k = logs[R - L + 1];
    return max(mx[L][k], mx[R - (1 << k) + 1][k]);
  };
  auto FirstL = [&](int p, int h) {
    int low = 0, high = p, idx = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (Query(mid, p) >= h) {
        idx = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return idx;
  };
  auto FirstR = [&](int p, int h) {
    int low = p, high = n - 1, idx = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (Query(p, mid) >= h) {
        idx = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return idx;
  };
  vector<array<int, 3>> seg;
  for (int i = 0; i < m; i++) {
    seg.push_back({l[i], r[i], y[i]});
    if (l[i] < s && s < r[i]) {
      int p = FirstL(s, y[i]);
      int q = FirstR(s, y[i]);
      if (p != l[i]) {
        seg.push_back({l[i], p, y[i]});
      }
      if (p != q) {
        seg.push_back({p, q, y[i]});
      }
      if (q != r[i]) {
        seg.push_back({q, r[i], y[i]});
      }
    }
    if (l[i] < f && f < r[i]) {
      int p = FirstL(f, y[i]);
      int q = FirstR(f, y[i]);
      if (p != l[i]) {
        seg.push_back({l[i], p, y[i]});
      }
      if (p != q) {
        seg.push_back({p, q, y[i]});
      }
      if (q != r[i]) {
        seg.push_back({q, r[i], y[i]});
      }
    }
  }
  l.clear();
  r.clear();
  y.clear();
  m = (int) seg.size();
  for (int i = 0; i < m; i++) {
    l.push_back(seg[i][0]);
    r.push_back(seg[i][1]);
    y.push_back(seg[i][2]);
  }
  vector<pair<int, int>> ver;
  for (int i = 0; i < n; i++) {
    ver.emplace_back(i, 0);
    ver.emplace_back(i, h[i]);
  }
  for (int i = 0; i < m; i++) {
    ver.emplace_back(l[i], y[i]);
    ver.emplace_back(r[i], y[i]);
  }
  vector<vector<int>> qs(n);
  for (int i = 0; i < m; i++) {
    qs[l[i]].push_back(y[i]);
    qs[r[i]].push_back(~y[i]);
  }
  multiset<int> st;
  for (int i = 0; i < n; i++) {
    for (int j : qs[i]) {
      if (j >= 0) {
        auto it = st.lower_bound(j);
        if (it != st.end()) {
          ver.emplace_back(i, *it);
        }
        if (it != st.begin()) {
          ver.emplace_back(i, *prev(it));
        }
        st.insert(j);
      }
    }
    for (int j : qs[i]) {
      if (j < 0) {
        j = ~j;
        auto it = st.lower_bound(j);
        if (it != prev(st.end())) {
          ver.emplace_back(i, *next(it));
        }
        if (it != st.begin()) {
          ver.emplace_back(i, *prev(it));
        }
        st.erase(it);
      }
    }
  }
  vector<pair<int, int>> new_ver;
  for (auto& p : ver) {
    if (h[p.first] >= p.second) {
      new_ver.push_back(p);
    }
  }
  ver = new_ver;
  sort(ver.begin(), ver.end());
  ver.erase(unique(ver.begin(), ver.end()), ver.end());
  auto Index = [&](int i, int h) {
    return (int) (lower_bound(ver.begin(), ver.end(), make_pair(i, h)) - ver.begin());
  };
  int k = (int) ver.size();
  vector<vector<pair<int, int>>> g(k);
  auto Add = [&](int from, int to, int cost) {
    g[from].emplace_back(to, cost);
    g[to].emplace_back(from, cost);
  };
  for (int i = 0; i + 1 < k; i++) {
    if (ver[i + 1].first == ver[i].first) {
      Add(i, i + 1, ver[i + 1].second - ver[i].second);
    }
  }
  map<int, vector<int>> mp;
  for (int i = 0; i < k; i++) {
    mp[ver[i].second].push_back(i);
  }
  for (auto& p : mp) {
    sort(p.second.begin(), p.second.end(), [&](int i, int j) {
      return ver[i].first < ver[j].first;
    });
  }
  for (int i = 0; i < m; i++) {
    int low = 0, high = (int) mp[y[i]].size() - 1, pos = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (ver[mp[y[i]][mid]].first >= l[i]) {
        pos = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    while (ver[mp[y[i]][pos]].first != r[i]) {
      Add(mp[y[i]][pos], mp[y[i]][pos + 1], x[ver[mp[y[i]][pos + 1]].first] - x[ver[mp[y[i]][pos]].first]);
      pos += 1;
    }
  }
  const long long inf = (long long) 1e18;
  vector<long long> dist(k, inf);
  dist[Index(s, 0)] = 0;
  set<pair<long long, int>> que;
  que.emplace(0, Index(s, 0));
  while (!que.empty()) {
    auto it = que.begin();
    int i = it->second;
    que.erase(it);
    for (auto &e : g[i]) {
      int to = e.first;
      int w = e.second;
      if (dist[to] > dist[i] + w) {
        if (dist[to] != inf) {
          que.erase({dist[to], to});
        }
        dist[to] = dist[i] + w;
        que.emplace(dist[to], to);
      }
    }
  }
  long long res = dist[Index(f, 0)];
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct

Subtask #2

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	432 KB	Output is correct
3	Correct	712 ms	70264 KB	Output is correct
4	Correct	875 ms	114184 KB	Output is correct
5	Correct	567 ms	96408 KB	Output is correct
6	Correct	539 ms	96416 KB	Output is correct
7	Correct	522 ms	98284 KB	Output is correct
8	Correct	740 ms	73896 KB	Output is correct
9	Correct	676 ms	102528 KB	Output is correct
10	Correct	867 ms	114320 KB	Output is correct
11	Correct	540 ms	75172 KB	Output is correct
12	Correct	459 ms	91796 KB	Output is correct
13	Correct	784 ms	117036 KB	Output is correct
14	Correct	469 ms	91284 KB	Output is correct
15	Correct	419 ms	69656 KB	Output is correct
16	Correct	261 ms	62012 KB	Output is correct
17	Correct	241 ms	61316 KB	Output is correct
18	Correct	392 ms	87736 KB	Output is correct
19	Correct	12 ms	4268 KB	Output is correct
20	Correct	141 ms	40428 KB	Output is correct
21	Correct	180 ms	53804 KB	Output is correct
22	Correct	205 ms	63272 KB	Output is correct
23	Correct	409 ms	79288 KB	Output is correct
24	Correct	235 ms	61548 KB	Output is correct
25	Correct	194 ms	59176 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	16700 KB	Output is correct
2	Correct	744 ms	81336 KB	Output is correct
3	Correct	803 ms	84428 KB	Output is correct
4	Correct	1046 ms	119044 KB	Output is correct
5	Correct	1178 ms	122548 KB	Output is correct
6	Correct	993 ms	118976 KB	Output is correct
7	Correct	512 ms	76944 KB	Output is correct
8	Correct	359 ms	74908 KB	Output is correct
9	Correct	988 ms	112784 KB	Output is correct
10	Correct	389 ms	83780 KB	Output is correct
11	Correct	24 ms	16724 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	16700 KB	Output is correct
2	Correct	744 ms	81336 KB	Output is correct
3	Correct	803 ms	84428 KB	Output is correct
4	Correct	1046 ms	119044 KB	Output is correct
5	Correct	1178 ms	122548 KB	Output is correct
6	Correct	993 ms	118976 KB	Output is correct
7	Correct	512 ms	76944 KB	Output is correct
8	Correct	359 ms	74908 KB	Output is correct
9	Correct	988 ms	112784 KB	Output is correct
10	Correct	389 ms	83780 KB	Output is correct
11	Correct	24 ms	16724 KB	Output is correct
12	Correct	841 ms	86652 KB	Output is correct
13	Correct	867 ms	125600 KB	Output is correct
14	Correct	1196 ms	134968 KB	Output is correct
15	Correct	673 ms	94384 KB	Output is correct
16	Correct	792 ms	109704 KB	Output is correct
17	Correct	904 ms	122544 KB	Output is correct
18	Correct	664 ms	94648 KB	Output is correct
19	Correct	768 ms	111404 KB	Output is correct
20	Correct	592 ms	86520 KB	Output is correct
21	Correct	104 ms	44236 KB	Output is correct
22	Correct	605 ms	101944 KB	Output is correct
23	Correct	528 ms	100572 KB	Output is correct
24	Correct	454 ms	82044 KB	Output is correct
25	Correct	526 ms	98092 KB	Output is correct
26	Correct	365 ms	74680 KB	Output is correct
27	Correct	1205 ms	132288 KB	Output is correct
28	Correct	844 ms	125120 KB	Output is correct
29	Correct	1105 ms	125720 KB	Output is correct
30	Correct	590 ms	87624 KB	Output is correct
31	Correct	1026 ms	125364 KB	Output is correct
32	Correct	310 ms	67216 KB	Output is correct
33	Correct	282 ms	72632 KB	Output is correct
34	Correct	362 ms	79800 KB	Output is correct
35	Correct	415 ms	77900 KB	Output is correct
36	Correct	318 ms	67564 KB	Output is correct
37	Correct	190 ms	51928 KB	Output is correct
38	Correct	206 ms	59944 KB	Output is correct
39	Correct	402 ms	77848 KB	Output is correct
40	Correct	253 ms	58356 KB	Output is correct
41	Correct	208 ms	54984 KB	Output is correct

Subtask #5

43.0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	432 KB	Output is correct
20	Correct	712 ms	70264 KB	Output is correct
21	Correct	875 ms	114184 KB	Output is correct
22	Correct	567 ms	96408 KB	Output is correct
23	Correct	539 ms	96416 KB	Output is correct
24	Correct	522 ms	98284 KB	Output is correct
25	Correct	740 ms	73896 KB	Output is correct
26	Correct	676 ms	102528 KB	Output is correct
27	Correct	867 ms	114320 KB	Output is correct
28	Correct	540 ms	75172 KB	Output is correct
29	Correct	459 ms	91796 KB	Output is correct
30	Correct	784 ms	117036 KB	Output is correct
31	Correct	469 ms	91284 KB	Output is correct
32	Correct	419 ms	69656 KB	Output is correct
33	Correct	261 ms	62012 KB	Output is correct
34	Correct	241 ms	61316 KB	Output is correct
35	Correct	392 ms	87736 KB	Output is correct
36	Correct	12 ms	4268 KB	Output is correct
37	Correct	141 ms	40428 KB	Output is correct
38	Correct	180 ms	53804 KB	Output is correct
39	Correct	205 ms	63272 KB	Output is correct
40	Correct	409 ms	79288 KB	Output is correct
41	Correct	235 ms	61548 KB	Output is correct
42	Correct	194 ms	59176 KB	Output is correct
43	Correct	68 ms	16700 KB	Output is correct
44	Correct	744 ms	81336 KB	Output is correct
45	Correct	803 ms	84428 KB	Output is correct
46	Correct	1046 ms	119044 KB	Output is correct
47	Correct	1178 ms	122548 KB	Output is correct
48	Correct	993 ms	118976 KB	Output is correct
49	Correct	512 ms	76944 KB	Output is correct
50	Correct	359 ms	74908 KB	Output is correct
51	Correct	988 ms	112784 KB	Output is correct
52	Correct	389 ms	83780 KB	Output is correct
53	Correct	24 ms	16724 KB	Output is correct
54	Correct	841 ms	86652 KB	Output is correct
55	Correct	867 ms	125600 KB	Output is correct
56	Correct	1196 ms	134968 KB	Output is correct
57	Correct	673 ms	94384 KB	Output is correct
58	Correct	792 ms	109704 KB	Output is correct
59	Correct	904 ms	122544 KB	Output is correct
60	Correct	664 ms	94648 KB	Output is correct
61	Correct	768 ms	111404 KB	Output is correct
62	Correct	592 ms	86520 KB	Output is correct
63	Correct	104 ms	44236 KB	Output is correct
64	Correct	605 ms	101944 KB	Output is correct
65	Correct	528 ms	100572 KB	Output is correct
66	Correct	454 ms	82044 KB	Output is correct
67	Correct	526 ms	98092 KB	Output is correct
68	Correct	365 ms	74680 KB	Output is correct
69	Correct	1205 ms	132288 KB	Output is correct
70	Correct	844 ms	125120 KB	Output is correct
71	Correct	1105 ms	125720 KB	Output is correct
72	Correct	590 ms	87624 KB	Output is correct
73	Correct	1026 ms	125364 KB	Output is correct
74	Correct	310 ms	67216 KB	Output is correct
75	Correct	282 ms	72632 KB	Output is correct
76	Correct	362 ms	79800 KB	Output is correct
77	Correct	415 ms	77900 KB	Output is correct
78	Correct	318 ms	67564 KB	Output is correct
79	Correct	190 ms	51928 KB	Output is correct
80	Correct	206 ms	59944 KB	Output is correct
81	Correct	402 ms	77848 KB	Output is correct
82	Correct	253 ms	58356 KB	Output is correct
83	Correct	208 ms	54984 KB	Output is correct
84	Correct	59 ms	13184 KB	Output is correct
85	Correct	927 ms	93980 KB	Output is correct
86	Correct	1586 ms	177164 KB	Output is correct
87	Correct	105 ms	45328 KB	Output is correct
88	Correct	133 ms	56428 KB	Output is correct
89	Correct	108 ms	45332 KB	Output is correct
90	Correct	22 ms	6932 KB	Output is correct
91	Correct	2 ms	860 KB	Output is correct
92	Correct	30 ms	8092 KB	Output is correct
93	Correct	454 ms	77716 KB	Output is correct
94	Correct	105 ms	46680 KB	Output is correct
95	Correct	664 ms	109396 KB	Output is correct
96	Correct	630 ms	104864 KB	Output is correct
97	Correct	520 ms	91564 KB	Output is correct
98	Correct	527 ms	103968 KB	Output is correct
99	Correct	2150 ms	218640 KB	Output is correct
100	Correct	1119 ms	140116 KB	Output is correct
101	Correct	1384 ms	163344 KB	Output is correct
102	Correct	613 ms	96600 KB	Output is correct
103	Correct	306 ms	71412 KB	Output is correct
104	Correct	291 ms	74528 KB	Output is correct
105	Correct	407 ms	78884 KB	Output is correct
106	Correct	351 ms	79384 KB	Output is correct
107	Correct	379 ms	73900 KB	Output is correct
108	Correct	49 ms	11080 KB	Output is correct
109	Correct	829 ms	111720 KB	Output is correct
110	Correct	895 ms	131832 KB	Output is correct
111	Correct	817 ms	131364 KB	Output is correct
112	Correct	368 ms	77560 KB	Output is correct
113	Correct	342 ms	75496 KB	Output is correct