oj.uz

Submission #418658

# Submission time Handle Problem Language Result Execution time Memory
418658 2021-06-05T16:53:01 Z usachevd0 Sky Walking (IOI19_walk) C++17
100 / 100
 1759 ms 225932 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef LOCAL
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& e : v) {
    stream << e << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}


const ll INF64 = 1e18;
#ifdef LOCAL
  const int maxN = 50;
  const int maxV = 150;
#else
  const int maxN = 1e5 + 5;
  const int maxV = 4e6 + 6;
#endif
int n, m;

int V;
vector<pii> G[maxV];
ll dist[maxV];
priority_queue<pli> pq;

set<int> points[maxN];
map<int, int> ptIdx[maxN];
int getIdx(int i, int y) {
  if (ptIdx[i].count(y))
    return ptIdx[i][y];
  return ptIdx[i][y] = V++;
}

void addEdge(int u, int v, int w) {
  G[u].emplace_back(v, w);
  G[v].emplace_back(u, w);
}

namespace sgt {
  const int logN = 17;
  const int N = 1 << logN;
  int mx[2 * N];
  
  void build(vector<int>& H) {
    for (int i = 0; i < n; ++i)
      mx[i + N] = H[i];
    for (int i = N - 1; i >= 1; --i)
      mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
  }
  
  int getFirstGeq(int v, int vl, int vr, int l, int r, int x) {
    if (l > r || vr < l || r < vl || mx[v] < x) return -1;
    if (vl == vr) return vl;
    int vm = (vl + vr) >> 1;
    int al = getFirstGeq(v << 1, vl, vm, l, r, x);
    if (al != -1)
      return al;
    return getFirstGeq(v << 1 | 1, vm + 1, vr, l, r, x);
  }
  int getFirstGeq(int l, int r, int x) {
    return getFirstGeq(1, 0, N - 1, l, r, x);
  }
  
  int getLastGeq(int v, int vl, int vr, int l, int r, int x) {
    if (l > r || vr < l || r < vl || mx[v] < x) return -1;
    if (vl == vr) return vl;
    int vm = (vl + vr) >> 1;
    int ar = getLastGeq(v << 1 | 1, vm + 1, vr, l, r, x);
    if (ar != -1)
      return ar;
    return getLastGeq(v << 1, vl, vm, l, r, x);
  }
  int getLastGeq(int l, int r, int x) {
    return getLastGeq(1, 0, N - 1, l, r, x);
  }
}

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int si, int ti) {
  n = X.size(), m = L.size();
  int S, T;
  for (int i = 0; i < n; ++i) {
    int v = getIdx(i, 0);
    if (i == si)
      S = v;
    if (i == ti)
      T = v;
  }
  sgt::build(H);
  struct Event {
    int i, tp, j;
    
    Event() {}
    Event(int _i, int _tp, int _j): i(_i), tp(_tp), j(_j) {}
    
    bool operator < (const Event& e) const {
      if (i != e.i)
        return i < e.i;
      return tp < e.tp;
    }
  };
  vector<Event> ev;
  for (int j = 0; j < m; ++j) {
    int l = L[j], r = R[j], y = Y[j];
    auto& p = points[j];
    p.insert(l);
    p.insert(r);
    for (int i : {si, ti}) {
      if (i <= r)
        p.insert(sgt::getFirstGeq(max(l, i), r, y));
      if (i >= l)
        p.insert(sgt::getLastGeq(l, min(r, i), y));
    }
    ev.emplace_back(l + 1, 0, j);
    ev.emplace_back(r, 1, j);
    for (int i : p)
      ev.emplace_back(i, 2, j);
  }
  sort(all(ev));
  set<pii> open;
  for (auto& e : ev) {
    if (e.tp == 0) {
      open.insert({Y[e.j], e.j});
    } else if (e.tp == 1) {
      open.erase({Y[e.j], e.j});
    } else {
      int y = Y[e.j];
      // debug(e.i, y, e.j);
      // for (auto el : open) cerr << el << ";  "; cerr << endl;
      auto it = open.lower_bound({y, -1});
      if (it != open.begin()) {
        it = prev(it);
        int y1 = it->fi;
        int j1 = it->se;
        getIdx(e.i, y1);
        points[j1].insert(e.i);
      }
    }
  }
  for (int j = 0; j < m; ++j) {
    // debug(j);
    // for (auto i : points[j])
    //   cerr << i << ' ';
    // cerr << endl;
    int y = Y[j];
    int last_i = -1;
    int last_v = -1;
    for (int i : points[j]) {
      int v = getIdx(i, y);
      if (last_i != -1) {
        addEdge(last_v, v, X[i] - X[last_i]);
      }
      last_i = i;
      last_v = v;
    }
  }
  for (int i = 0; i < n; ++i) {
    int last_v = -1;
    int last_y = -1;
    // debug(i);
    for (auto& [y, v] : ptIdx[i]) {
      // cerr << y << ' ';
      if (last_v != -1) {
        addEdge(last_v, v, y - last_y);
      }
      last_v = v;
      last_y = y;
    }
    // cerr << endl;
  }
  fill(dist, dist + V, INF64);
  dist[S] = 0;
  pq.push({0, S});
  while (!pq.empty()) {
    int v = pq.top().se;
    ll d = -pq.top().fi;
    pq.pop();
    if (d != dist[v]) continue;
    if (v == T) return dist[v];
    for (auto& [u, w] : G[v])
      if (chkmin(dist[u], dist[v] + w))
        pq.push({-dist[u], u});
  }
  return -1;
}


#ifdef LOCAL
int32_t main() {
  #ifdef LOCAL
    freopen("in", "r", stdin);
  #endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int n, m;
  assert(2 == scanf("%d%d", &n, &m));
  vector<int> x(n), h(n);
  for (int i = 0; i < n; i++)
    assert(2 == scanf("%d%d", &x[i], &h[i]));
  vector<int> l(m), r(m), y(m);
  for (int i = 0; i < m; i++)
    assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
  int s, g;
  assert(2 == scanf("%d%d", &s, &g));
  fclose(stdin);

  long long result = min_distance(x, h, l, r, y, s, g);

  printf("%lld\n", result);
  fclose(stdout);
  
  return 0;
}
#endif

Compilation message

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:222:5: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |     if (v == T) return dist[v];
      |     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104004 KB Output is correct
2 Correct 59 ms 104020 KB Output is correct
3 Correct 59 ms 104112 KB Output is correct
4 Correct 60 ms 104112 KB Output is correct
5 Correct 58 ms 104132 KB Output is correct
6 Correct 61 ms 104060 KB Output is correct
7 Correct 62 ms 104072 KB Output is correct
8 Correct 64 ms 104132 KB Output is correct
9 Correct 60 ms 104132 KB Output is correct
10 Correct 64 ms 104100 KB Output is correct
11 Correct 61 ms 104032 KB Output is correct
12 Correct 63 ms 104136 KB Output is correct
13 Correct 65 ms 104148 KB Output is correct
14 Correct 62 ms 104112 KB Output is correct
15 Correct 60 ms 104084 KB Output is correct
16 Correct 61 ms 104072 KB Output is correct
17 Correct 67 ms 104168 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 104064 KB Output is correct
2 Correct 59 ms 104084 KB Output is correct
3 Correct 667 ms 165316 KB Output is correct
4 Correct 725 ms 173508 KB Output is correct
5 Correct 464 ms 160548 KB Output is correct
6 Correct 462 ms 158232 KB Output is correct
7 Correct 488 ms 160972 KB Output is correct
8 Correct 778 ms 170428 KB Output is correct
9 Correct 636 ms 172404 KB Output is correct
10 Correct 803 ms 178632 KB Output is correct
11 Correct 588 ms 162084 KB Output is correct
12 Correct 418 ms 154116 KB Output is correct
13 Correct 751 ms 181112 KB Output is correct
14 Correct 469 ms 150644 KB Output is correct
15 Correct 484 ms 153128 KB Output is correct
16 Correct 481 ms 154988 KB Output is correct
17 Correct 429 ms 152568 KB Output is correct
18 Correct 580 ms 156260 KB Output is correct
19 Correct 75 ms 106404 KB Output is correct
20 Correct 188 ms 128020 KB Output is correct
21 Correct 403 ms 152020 KB Output is correct
22 Correct 363 ms 153064 KB Output is correct
23 Correct 705 ms 164896 KB Output is correct
24 Correct 440 ms 153572 KB Output is correct
25 Correct 423 ms 152500 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 120048 KB Output is correct
2 Correct 1002 ms 174180 KB Output is correct
3 Correct 1093 ms 176552 KB Output is correct
4 Correct 1096 ms 185612 KB Output is correct
5 Correct 1306 ms 188476 KB Output is correct
6 Correct 1168 ms 186964 KB Output is correct
7 Correct 501 ms 151156 KB Output is correct
8 Correct 417 ms 154056 KB Output is correct
9 Correct 1139 ms 183632 KB Output is correct
10 Correct 473 ms 154216 KB Output is correct
11 Correct 77 ms 108652 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 120048 KB Output is correct
2 Correct 1002 ms 174180 KB Output is correct
3 Correct 1093 ms 176552 KB Output is correct
4 Correct 1096 ms 185612 KB Output is correct
5 Correct 1306 ms 188476 KB Output is correct
6 Correct 1168 ms 186964 KB Output is correct
7 Correct 501 ms 151156 KB Output is correct
8 Correct 417 ms 154056 KB Output is correct
9 Correct 1139 ms 183632 KB Output is correct
10 Correct 473 ms 154216 KB Output is correct
11 Correct 77 ms 108652 KB Output is correct
12 Correct 1094 ms 178644 KB Output is correct
13 Correct 835 ms 187980 KB Output is correct
14 Correct 1199 ms 192092 KB Output is correct
15 Correct 799 ms 177472 KB Output is correct
16 Correct 858 ms 177308 KB Output is correct
17 Correct 916 ms 187228 KB Output is correct
18 Correct 788 ms 177440 KB Output is correct
19 Correct 839 ms 177268 KB Output is correct
20 Correct 518 ms 150384 KB Output is correct
21 Correct 103 ms 114116 KB Output is correct
22 Correct 653 ms 172420 KB Output is correct
23 Correct 593 ms 170716 KB Output is correct
24 Correct 455 ms 158312 KB Output is correct
25 Correct 553 ms 166388 KB Output is correct
26 Correct 405 ms 150632 KB Output is correct
27 Correct 1267 ms 192052 KB Output is correct
28 Correct 737 ms 187564 KB Output is correct
29 Correct 1209 ms 185612 KB Output is correct
30 Correct 492 ms 150892 KB Output is correct
31 Correct 1049 ms 182888 KB Output is correct
32 Correct 453 ms 152560 KB Output is correct
33 Correct 405 ms 153620 KB Output is correct
34 Correct 594 ms 158984 KB Output is correct
35 Correct 573 ms 160976 KB Output is correct
36 Correct 437 ms 155696 KB Output is correct
37 Correct 394 ms 152176 KB Output is correct
38 Correct 350 ms 153040 KB Output is correct
39 Correct 678 ms 164968 KB Output is correct
40 Correct 438 ms 153704 KB Output is correct
41 Correct 431 ms 152424 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104004 KB Output is correct
2 Correct 59 ms 104020 KB Output is correct
3 Correct 59 ms 104112 KB Output is correct
4 Correct 60 ms 104112 KB Output is correct
5 Correct 58 ms 104132 KB Output is correct
6 Correct 61 ms 104060 KB Output is correct
7 Correct 62 ms 104072 KB Output is correct
8 Correct 64 ms 104132 KB Output is correct
9 Correct 60 ms 104132 KB Output is correct
10 Correct 64 ms 104100 KB Output is correct
11 Correct 61 ms 104032 KB Output is correct
12 Correct 63 ms 104136 KB Output is correct
13 Correct 65 ms 104148 KB Output is correct
14 Correct 62 ms 104112 KB Output is correct
15 Correct 60 ms 104084 KB Output is correct
16 Correct 61 ms 104072 KB Output is correct
17 Correct 67 ms 104168 KB Output is correct
18 Correct 60 ms 104064 KB Output is correct
19 Correct 59 ms 104084 KB Output is correct
20 Correct 667 ms 165316 KB Output is correct
21 Correct 725 ms 173508 KB Output is correct
22 Correct 464 ms 160548 KB Output is correct
23 Correct 462 ms 158232 KB Output is correct
24 Correct 488 ms 160972 KB Output is correct
25 Correct 778 ms 170428 KB Output is correct
26 Correct 636 ms 172404 KB Output is correct
27 Correct 803 ms 178632 KB Output is correct
28 Correct 588 ms 162084 KB Output is correct
29 Correct 418 ms 154116 KB Output is correct
30 Correct 751 ms 181112 KB Output is correct
31 Correct 469 ms 150644 KB Output is correct
32 Correct 484 ms 153128 KB Output is correct
33 Correct 481 ms 154988 KB Output is correct
34 Correct 429 ms 152568 KB Output is correct
35 Correct 580 ms 156260 KB Output is correct
36 Correct 75 ms 106404 KB Output is correct
37 Correct 188 ms 128020 KB Output is correct
38 Correct 403 ms 152020 KB Output is correct
39 Correct 363 ms 153064 KB Output is correct
40 Correct 705 ms 164896 KB Output is correct
41 Correct 440 ms 153572 KB Output is correct
42 Correct 423 ms 152500 KB Output is correct
43 Correct 174 ms 120048 KB Output is correct
44 Correct 1002 ms 174180 KB Output is correct
45 Correct 1093 ms 176552 KB Output is correct
46 Correct 1096 ms 185612 KB Output is correct
47 Correct 1306 ms 188476 KB Output is correct
48 Correct 1168 ms 186964 KB Output is correct
49 Correct 501 ms 151156 KB Output is correct
50 Correct 417 ms 154056 KB Output is correct
51 Correct 1139 ms 183632 KB Output is correct
52 Correct 473 ms 154216 KB Output is correct
53 Correct 77 ms 108652 KB Output is correct
54 Correct 1094 ms 178644 KB Output is correct
55 Correct 835 ms 187980 KB Output is correct
56 Correct 1199 ms 192092 KB Output is correct
57 Correct 799 ms 177472 KB Output is correct
58 Correct 858 ms 177308 KB Output is correct
59 Correct 916 ms 187228 KB Output is correct
60 Correct 788 ms 177440 KB Output is correct
61 Correct 839 ms 177268 KB Output is correct
62 Correct 518 ms 150384 KB Output is correct
63 Correct 103 ms 114116 KB Output is correct
64 Correct 653 ms 172420 KB Output is correct
65 Correct 593 ms 170716 KB Output is correct
66 Correct 455 ms 158312 KB Output is correct
67 Correct 553 ms 166388 KB Output is correct
68 Correct 405 ms 150632 KB Output is correct
69 Correct 1267 ms 192052 KB Output is correct
70 Correct 737 ms 187564 KB Output is correct
71 Correct 1209 ms 185612 KB Output is correct
72 Correct 492 ms 150892 KB Output is correct
73 Correct 1049 ms 182888 KB Output is correct
74 Correct 453 ms 152560 KB Output is correct
75 Correct 405 ms 153620 KB Output is correct
76 Correct 594 ms 158984 KB Output is correct
77 Correct 573 ms 160976 KB Output is correct
78 Correct 437 ms 155696 KB Output is correct
79 Correct 394 ms 152176 KB Output is correct
80 Correct 350 ms 153040 KB Output is correct
81 Correct 678 ms 164968 KB Output is correct
82 Correct 438 ms 153704 KB Output is correct
83 Correct 431 ms 152424 KB Output is correct
84 Correct 156 ms 117496 KB Output is correct
85 Correct 1029 ms 180932 KB Output is correct
86 Correct 1369 ms 206272 KB Output is correct
87 Correct 132 ms 119292 KB Output is correct
88 Correct 132 ms 119232 KB Output is correct
89 Correct 129 ms 119196 KB Output is correct
90 Correct 90 ms 109180 KB Output is correct
91 Correct 66 ms 104228 KB Output is correct
92 Correct 82 ms 107664 KB Output is correct
93 Correct 341 ms 138480 KB Output is correct
94 Correct 104 ms 114372 KB Output is correct
95 Correct 673 ms 175940 KB Output is correct
96 Correct 601 ms 171272 KB Output is correct
97 Correct 470 ms 158184 KB Output is correct
98 Correct 569 ms 166248 KB Output is correct
99 Correct 1759 ms 225932 KB Output is correct
100 Correct 985 ms 188880 KB Output is correct
101 Correct 1245 ms 196332 KB Output is correct
102 Correct 433 ms 150900 KB Output is correct
103 Correct 448 ms 152416 KB Output is correct
104 Correct 416 ms 153480 KB Output is correct
105 Correct 577 ms 158332 KB Output is correct
106 Correct 482 ms 153576 KB Output is correct
107 Correct 641 ms 158144 KB Output is correct
108 Correct 108 ms 110720 KB Output is correct
109 Correct 901 ms 171948 KB Output is correct
110 Correct 879 ms 187920 KB Output is correct
111 Correct 798 ms 187796 KB Output is correct
112 Correct 586 ms 160168 KB Output is correct
113 Correct 498 ms 158092 KB Output is correct