oj.uz

Submission #341576

# Submission time Handle Problem Language Result Execution time Memory
341576 2020-12-30T05:05:45 Z KoD Golf (JOI17_golf) C++17
30 / 100
 993 ms 1048580 KB 
#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <deque>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 17 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

template <class T>
using Vec = std::vector<T>;

struct Compressor {
  Vec<i32> data;
  Compressor(const usize size = 0) {
    data.reserve(size);
  }
  void add(const i32 x) {
    data.push_back(x);
  }
  void compress() {
    std::sort(data.begin(), data.end());
    data.erase(std::unique(data.begin(), data.end()), data.end());
  }
  i32 fix(const i32 x) const {
    return std::lower_bound(data.begin(), data.end(), x) - data.begin();
  }
  usize size() const {
    return data.size();
  }
};

int main() {
  i32 S, T, U, V;
  std::cin >> S >> T >> U >> V;
  usize N;
  std::cin >> N;
  Compressor Xc(2 * N + 4), Yc(2 * N + 4);
  Xc.add(S);
  Xc.add(U);
  Xc.add(0);
  Xc.add(1000000001);
  Yc.add(T);
  Yc.add(V);
  Yc.add(0);
  Yc.add(1000000001);
  Vec<i32> A(N), B(N), C(N), D(N);
  for (auto i: range(0, N)) {
    std::cin >> A[i] >> B[i] >> C[i] >> D[i];
    Xc.add(A[i]);
    Xc.add(B[i]);
    Yc.add(C[i]);
    Yc.add(D[i]);
  }
  Xc.compress();
  Yc.compress();
  S = Xc.fix(S);
  U = Xc.fix(U);
  T = Yc.fix(T);
  V = Yc.fix(V);
  for (auto i: range(0, N)) {
    A[i] = Xc.fix(A[i]);
    B[i] = Xc.fix(B[i]);
    C[i] = Yc.fix(C[i]);
    D[i] = Yc.fix(D[i]);
  }
  Vec<Vec<isize>> block(Xc.size(), Vec<isize>(Yc.size()));
  for (auto i: range(0, N)) {
    block[A[i]][C[i]] += 1;
    block[A[i]][D[i]] -= 1;
    block[B[i]][C[i]] -= 1;
    block[B[i]][D[i]] += 1;
  }
  for (auto i: range(0, Xc.size())) {
    for (auto j: range(0, Yc.size())) {
      if (i > 0) {
        block[i][j] += block[i - 1][j];
      }
      if (j > 0) {
        block[i][j] += block[i][j - 1];
      }
      if (i > 0 && j > 0) {
        block[i][j] -= block[i - 1][j - 1];
      }
    }
  }
  Vec<Vec<std::array<usize, 4>>> dist(Xc.size(), Vec<std::array<usize, 4>>(Yc.size()));
  for (auto &a: dist) {
    for (auto &b: a) {
      b.fill(inf32);
    }
  }
  std::deque<std::tuple<usize, usize, isize>> que;
  const auto push = [&](const usize x, const usize y, const usize k, const usize d, const bool to_back) {
    if (dist[x][y][k] > d) {
      dist[x][y][k] = d;
      if (to_back) {
        que.emplace_back(x, y, k);
      }
      else {
        que.emplace_front(x, y, k);
      }
    }
  };
  for (auto k: range(0, 4)) {
    push(S, T, k, 1, true);
  }
  while (!que.empty()) {
    const auto [x, y, k] = que.front();
    que.pop_front();
    std::array<usize, 4> next;
    next.fill(dist[x][y][k] + 1);
    next[k] -= 1;
    if (x + 1 != Xc.size()) {
      if (block[x][y] == 0 || (y > 0 && block[x][y - 1] == 0)) {
        push(x + 1, y, 0, next[0], k != 0);
      }
    }
    if (x > 0) {
      if (block[x - 1][y] == 0 || (y > 0 && block[x - 1][y - 1] == 0)) {
        push(x - 1, y, 1, next[1], k != 1);
      }
    }
    if (y + 1 != Yc.size()) {
      if (block[x][y] == 0 || (x > 0 && block[x - 1][y] == 0)) {
        push(x, y + 1, 2, next[2], k != 2);
      }
    }
    if (y > 0) {
      if (block[x][y - 1] == 0 || (x > 0 && block[x - 1][y - 1] == 0)) {
        push(x, y - 1, 3, next[3], k != 3);
      }
    }
  }
  usize ans = inf32;
  for (auto k: range(0, 4)) {
    ans = std::min(ans, dist[U][V][k]);
  }
  std::cout << ans << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 70 ms 30576 KB Output is correct
6 Correct 59 ms 29804 KB Output is correct
7 Correct 69 ms 27648 KB Output is correct
8 Correct 62 ms 30572 KB Output is correct
9 Correct 60 ms 28524 KB Output is correct
10 Correct 80 ms 30316 KB Output is correct
11 Correct 78 ms 32512 KB Output is correct
12 Correct 63 ms 28652 KB Output is correct
13 Correct 57 ms 29676 KB Output is correct
14 Correct 68 ms 31276 KB Output is correct
15 Correct 23 ms 7020 KB Output is correct
16 Correct 106 ms 26240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 70 ms 30576 KB Output is correct
6 Correct 59 ms 29804 KB Output is correct
7 Correct 69 ms 27648 KB Output is correct
8 Correct 62 ms 30572 KB Output is correct
9 Correct 60 ms 28524 KB Output is correct
10 Correct 80 ms 30316 KB Output is correct
11 Correct 78 ms 32512 KB Output is correct
12 Correct 63 ms 28652 KB Output is correct
13 Correct 57 ms 29676 KB Output is correct
14 Correct 68 ms 31276 KB Output is correct
15 Correct 23 ms 7020 KB Output is correct
16 Correct 106 ms 26240 KB Output is correct
17 Correct 402 ms 181044 KB Output is correct
18 Correct 408 ms 182624 KB Output is correct
19 Correct 383 ms 175616 KB Output is correct
20 Correct 375 ms 180048 KB Output is correct
21 Correct 425 ms 188364 KB Output is correct
22 Correct 398 ms 185092 KB Output is correct
23 Correct 391 ms 180436 KB Output is correct
24 Correct 350 ms 177284 KB Output is correct
25 Correct 365 ms 180996 KB Output is correct
26 Correct 376 ms 178568 KB Output is correct
27 Correct 34 ms 9836 KB Output is correct
28 Correct 134 ms 31596 KB Output is correct
29 Correct 141 ms 32492 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 4 ms 2156 KB Output is correct
5 Correct 70 ms 30576 KB Output is correct
6 Correct 59 ms 29804 KB Output is correct
7 Correct 69 ms 27648 KB Output is correct
8 Correct 62 ms 30572 KB Output is correct
9 Correct 60 ms 28524 KB Output is correct
10 Correct 80 ms 30316 KB Output is correct
11 Correct 78 ms 32512 KB Output is correct
12 Correct 63 ms 28652 KB Output is correct
13 Correct 57 ms 29676 KB Output is correct
14 Correct 68 ms 31276 KB Output is correct
15 Correct 23 ms 7020 KB Output is correct
16 Correct 106 ms 26240 KB Output is correct
17 Correct 402 ms 181044 KB Output is correct
18 Correct 408 ms 182624 KB Output is correct
19 Correct 383 ms 175616 KB Output is correct
20 Correct 375 ms 180048 KB Output is correct
21 Correct 425 ms 188364 KB Output is correct
22 Correct 398 ms 185092 KB Output is correct
23 Correct 391 ms 180436 KB Output is correct
24 Correct 350 ms 177284 KB Output is correct
25 Correct 365 ms 180996 KB Output is correct
26 Correct 376 ms 178568 KB Output is correct
27 Correct 34 ms 9836 KB Output is correct
28 Correct 134 ms 31596 KB Output is correct
29 Correct 141 ms 32492 KB Output is correct
30 Runtime error 993 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -