제출 #1252164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252164		jerry	장애물 (IOI25_obstacles)	C++20	24 / 100	1092 ms	27064 KiB

obstacles

#include <assert.h>
#include <limits.h>
#include <memory>
#include <utility>
#include <vector>

class SegmentTree {
  public:
    SegmentTree(const std::vector<int>& data);

    int query_max(int l, int r) const;  // include-exclude
    int get_next_le(int from, int value) const;
    int get_prev_gt(int from, int value) const;

  private:
    int n;
    std::vector<int> max, min;
};

class SingleSideSolver {
  public:
    SingleSideSolver(const std::vector<int>& _t, const std::vector<int>& _h);

    bool can_reach(int l, int s, int d) const;

  private:
    int get_strictest_column(int l, int r) const;
    int get_leftmost_reachable_column(int s, int l) const;
    bool reduce_columns(const std::vector<int>& vals) const;

    const std::vector<int> t, h;
    const SegmentTree row_tree, col_tree;
};

std::unique_ptr<SingleSideSolver> left, right;
int n, m;

void initialize(std::vector<int> t, std::vector<int> h) {
  n = t.size();
  m = h.size();
  left = std::make_unique<SingleSideSolver>(t, h);
  right = std::make_unique<SingleSideSolver>(t, std::vector<int>(h.rbegin(), h.rend()));
}

bool can_reach(int l, int r, int s, int d) {
  if (s > d)
    std::swap(s, d);
  return left->can_reach(l, s, d) && right->can_reach(m - r - 1, m - d - 1, m - s - 1);
}

SegmentTree::SegmentTree(const std::vector<int>& data) {
  n = data.size() + 1;
  while (__builtin_popcount(n) > 1)
    n += n & -n;

  max = std::vector<int>(n * 2, INT_MAX);
  min = std::vector<int>(n * 2, INT_MIN);
  for (int i = 0; i < data.size(); i++)
    max[i + n] = min[i + n] = data[i];
  for (int i = n - 1; i > 0; i--) {
    max[i] = std::max(max[i * 2], max[i * 2 + 1]);
    min[i] = std::min(min[i * 2], min[i * 2 + 1]);
  }
}

int SegmentTree::query_max(int l, int r) const {
  int answer = INT_MIN;
  for (l += n, r += n; l != r; l /= 2, r /= 2) {
    if (l & 1)
      answer = std::max(answer, max[l++]);
    if (r & 1)
      answer = std::max(answer, max[--r]);
  }
  return answer;
}

int SegmentTree::get_next_le(int from, int value) const {
  from += n;
  while (min[from] > value) {
    if (from % 2 == 0)
      while (from % 2 == 0)
        from /= 2;
    else
      from++;
  }
  while (from < n) {
    from *= 2;
    if (min[from] > value)
      from++;
  }
  return from - n;
}

int SegmentTree::get_prev_gt(int from, int value) const {
  if (query_max(0, from + 1) <= value)
    return -1;
  from += n;
  while (max[from] <= value) {
    if (from % 2 == 1)
      while (from % 2 == 1)
        from /= 2;
    else
      from--;
  }
  while (from < n) {
    from *= 2;
    if (max[from + 1] > value)
      from++;
  }
  return from - n;
}

SingleSideSolver::SingleSideSolver(const std::vector<int>& _t, const std::vector<int>& _h)
  : t(_t), h(_h), row_tree(t), col_tree(h) {}

bool SingleSideSolver::can_reach(int l, int s, int d) const {
  const int col = get_leftmost_reachable_column(s, l);
  const int c1 = get_strictest_column(col, s);
  const int c2 = get_strictest_column(col, d);
  return reduce_columns({h[s], c1, h[col], c2, h[d]});
}

int SingleSideSolver::get_strictest_column(int l, int r) const {
  return col_tree.query_max(l, r + 1);
}

int SingleSideSolver::get_leftmost_reachable_column(int s, int l) const {
  int lo = l - 1, hi = s;
  while (lo + 1 < hi) {
    const int mid = (lo + hi) / 2;
    const int c = get_strictest_column(mid, s);
    if (reduce_columns({h[s], c, h[mid]}))
      hi = mid;
    else
      lo = mid;
  }
  return hi;
}

bool SingleSideSolver::reduce_columns(const std::vector<int>& vals) const {
  assert(t[0] > vals[0]);

  int max_depth = 0;
  for (int v : vals) {
    if (t[max_depth] > v)
      max_depth = row_tree.get_next_le(max_depth, v) - 1;
    else
      max_depth = row_tree.get_prev_gt(max_depth, v);
    if (max_depth < 0)
      return false;
  }
  return true;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17