Submission #341576

#	Time	Username	Problem	Language	Result	Execution time	Memory
341576		KoD	Golf (JOI17_golf)	C++17	30 / 100	993 ms	1048580 KiB

golf

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70