Submission #1317282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317282		madamadam3	Obstacles for a Llama (IOI25_obstacles)	C++20	44 / 100	2095 ms	22260 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));
  }
};

int r, c;
SegTree row, col;
vi t, h;
void initialize(vi T, vi H) {
  r = T.size(); c = H.size();
  t = T; h = H;
  row = SegTree(r, T); col = SegTree(c, H);
  return;
}

bool can_reach(int L, int R, 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 lo1 = 0, hi1 = x;
    // int lo2 = x, hi2 = c;

    // while (lo1 < hi1) {
    //   int mid = lo1 + (hi1 - lo1) / 2;
    //   if (h[col.query(0, 0, c, mid, x+1).second] < t[i]) hi1 = mid;
    //   else lo1 = mid + 1;
    // }

    // while (lo2 < hi2) {
    //   int mid = lo2 + (hi2 - lo2) / 2;
    //   if (h[col.query(0, 0, c, x, mid+1).second] < t[i]) lo2 = mid+1;
    //   else hi2 = mid;
    // }
    // return make_pair(lo1, lo2-1);

    int a = ca, b = cb;
    while (a > 0 && t[i] > h[a-1]) a--;
    while (b < c-1 && t[i] > h[b+1]) b++;
    return make_pair(a, b);
  };

  int ra = 0, rb = 0;
  int ca = s, cb = s, da = d, db = d;
  while (ra < first || rb < first) {
    if (ra < first) {
      auto range = get_range(ra, s, ca, cb);
      ca = range.first, cb = range.second;
      int best = col.query(0, 0, c, range.first, range.second+1).first;

      if (t[ra+1] <= h[best]) return false;
      ra++; s = best;
    } 
    if (rb < first) {
      auto range = get_range(rb, d, da, db);
      da = range.first, db = range.second;
      int best = col.query(0, 0, c, range.first, range.second+1).first;

      if (t[rb+1] <= h[best]) return false;
      rb++; d = best;
    }
  }
  
  return true;
}

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