oj.uz

Submission #418655

# Submission time Handle Problem Language Result Execution time Memory
418655 2021-06-05T16:51:46 Z usachevd0 Sky Walking (IOI19_walk) C++17
0 / 100
 1361 ms 188220 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 int 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:55:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   55 | const int INF64 = 1e18;
      |                   ^~~~
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104004 KB Output is correct
2 Correct 63 ms 104092 KB Output is correct
3 Correct 62 ms 104116 KB Output is correct
4 Correct 64 ms 104132 KB Output is correct
5 Correct 62 ms 104132 KB Output is correct
6 Correct 64 ms 104068 KB Output is correct
7 Correct 67 ms 104100 KB Output is correct
8 Correct 63 ms 104132 KB Output is correct
9 Correct 64 ms 104148 KB Output is correct
10 Correct 63 ms 104136 KB Output is correct
11 Correct 63 ms 104084 KB Output is correct
12 Correct 65 ms 104052 KB Output is correct
13 Correct 63 ms 104060 KB Output is correct
14 Correct 65 ms 104064 KB Output is correct
15 Correct 62 ms 104060 KB Output is correct
16 Incorrect 62 ms 104132 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 104040 KB Output is correct
2 Correct 62 ms 104108 KB Output is correct
3 Correct 659 ms 165352 KB Output is correct
4 Incorrect 651 ms 173640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 120072 KB Output is correct
2 Correct 1089 ms 174188 KB Output is correct
3 Correct 1117 ms 176364 KB Output is correct
4 Correct 1116 ms 185672 KB Output is correct
5 Incorrect 1361 ms 188220 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 120072 KB Output is correct
2 Correct 1089 ms 174188 KB Output is correct
3 Correct 1117 ms 176364 KB Output is correct
4 Correct 1116 ms 185672 KB Output is correct
5 Incorrect 1361 ms 188220 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104004 KB Output is correct
2 Correct 63 ms 104092 KB Output is correct
3 Correct 62 ms 104116 KB Output is correct
4 Correct 64 ms 104132 KB Output is correct
5 Correct 62 ms 104132 KB Output is correct
6 Correct 64 ms 104068 KB Output is correct
7 Correct 67 ms 104100 KB Output is correct
8 Correct 63 ms 104132 KB Output is correct
9 Correct 64 ms 104148 KB Output is correct
10 Correct 63 ms 104136 KB Output is correct
11 Correct 63 ms 104084 KB Output is correct
12 Correct 65 ms 104052 KB Output is correct
13 Correct 63 ms 104060 KB Output is correct
14 Correct 65 ms 104064 KB Output is correct
15 Correct 62 ms 104060 KB Output is correct
16 Incorrect 62 ms 104132 KB Output isn't correct
17 Halted 0 ms 0 KB -