제출 #1317649

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

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;

struct SegTree {
  int n; vi arr; vector<pi> st;
  SegTree() {}
  SegTree(int N, vi &Arr) {
    n = N; arr = Arr; st.assign(4*n, {-1, -1});
    build(0, 0, n);
  }

  pi combine(pi x, pi y) {
    pi r = {-1, -1};
    if (x.first < 0) r.first = y.first;
    else if (y.first < 0) r.first = x.first;
    else r.first = arr[x.first] < arr[y.first] ? x.first : y.first;
    
    if (x.second < 0) r.second = y.second;
    else if (y.second < 0) r.second = x.second;
    else r.second = arr[x.second] > arr[y.second] ? x.second : y.second;

    return r;
  }

  pi build(int i, int l, int r) {
    if (l+1==r) return st[i] = {l, l};
    int m = l + (r- l)/2;
    return st[i] = combine(build(2*i+1, l, m), build(2*i+2, m, r));
  }

  pi query(int i, int l, int r, int ql, int qr) {
    if (qr <= l || r <= ql) return {-1, -1};
    if (ql <= l && r <= qr) return st[i];

    int m = l + (r - l) / 2;
    return combine(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
  }

  // max i in [l, r] such that max([l, i]) < T or min([l, i]) > T
  int right(int i, int l, int r, int ql, int qr, int T, bool mx) {
    if (r <= ql || qr <= l) return -1;
    if (ql <= l && r <= qr) {
      if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1;
    }

    if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1;

    int m = l + (r - l) / 2;
    int left = right(2*i+1, l, m, ql, qr, T, mx);
    if (left != -1) return left;
    return right(2*i+2, m, r, ql, qr, T, mx);
  }
  // min i in [l, r] such that max([i, r]) < T or min([i, r]) > T
  int left(int i, int l, int r, int ql, int qr, int T, bool mx) {
    if (r <= ql || qr <= l) return -1;
    if (ql <= l && r <= qr) {
      if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1;
    }

    if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1;

    int m = l + (r - l) / 2;
    int right = left(2*i+2, m, r, ql, qr, T, mx);
    if (right != -1) return right;
    return left(2*i+1, l, m, ql, qr, T, mx);
  }
};

int r, c;
SegTree row, col;
vi t, h, depth, L, R;
void initialize(vi T, vi H) {
  r = T.size(); c = H.size();
  t = T; h = H; depth.assign(c, 0); for (int i = 0; i < c; i++) L.push_back(i), R.push_back(i);
  row = SegTree(r, T); col = SegTree(c, H);
  return;
}

bool can_reach(int lower, int upper, int s, int d) {
  if (s>d) swap(s, d);

  int mx = h[col.query(0, 0, c, s, d+1).second];
  int lo = 0, hi = r;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (t[row.query(0, 0, r, 0, mid+1).second] > mx) hi = mid;
    else lo = mid + 1;
  }

  int first = lo;
  if (first >= r || t[first] <= mx) return false;

  auto get_range = [&](int i, int x, int ca, int cb) {
    int a = col.left(0, 0, c, 0, ca+1, t[i], true), b = col.right(0, 0, c, cb, c, t[i], true);
    a = (a == -1) ? 0 : a+1; b = (b == -1) ? c-1 : b-1;
    return make_pair(a, b);
  };

  while (depth[s] < first || depth[d] < first) {
    if (depth[s] < first) {
      int ns = col.query(0, 0, c, L[s], R[s]+1).first;
      L[s] = L[ns] = min(L[s], L[ns]); R[s] = R[ns] = max(R[s], R[ns]); 
      depth[s] = depth[ns] = max(depth[s], depth[ns]);
      s = ns;
      
      int posx = row.right(0, 0, r, depth[s], r, h[s], false);
      if (posx == -1) posx = r-1;

      if (posx == depth[s]) return false;
      depth[s] = posx;

      int maxy = row.query(0, 0, r, 0, posx+1).second;
      auto range = get_range(maxy, s, L[s], R[s]);
      L[s] = range.first, R[s] = range.second;
    } 
    if (depth[d] < first) {
      int nd = col.query(0, 0, c, L[d], R[d]+1).first;
      L[d] = L[nd] = min(L[d], L[nd]); R[d] = R[nd] = max(R[d], R[nd]); 
      depth[d] = depth[nd] = max(depth[d], depth[nd]);
      d = nd;
      
      int posx = row.right(0, 0, r, depth[d], r, h[d], false);
      if (posx == -1) posx = r-1;

      if (posx == depth[d]) return false;
      depth[d] = posx;

      int maxy = row.query(0, 0, r, 0, posx+1).second;
      auto range = get_range(maxy, d, L[d], R[d]);
      L[d] = range.first, R[d] = range.second;
    } 
  }
  
  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