Submission #1255842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255842		nicolo_010	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2096 ms	18244 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

struct SegTree {
  v<int> tree;
  v<int> mx;

  SegTree() {}

  SegTree(int n) {
    tree.assign(4*n, 1e9);
    mx.assign(4*n, 0);
  }

  void build(int p, int l, int r, int i, int x) {
    if (l > i || r < i) return;
    if (l == r && r == i) {
      tree[p] = x;
      mx[p] = x;
    }
    else {
      build(2*p, l, (l+r)/2, i, x);
      build(2*p+1, (l+r)/2+1, r, i, x);
      tree[p] = min(tree[2*p], tree[2*p+1]);
      mx[p] = max(mx[2*p], mx[2*p+1]);
    }
  }

  int query(int p, int l, int r, int i, int j) {
    if (l > j || r < i) return 0;
    if (i <= l && r <= j) return tree[p];
    else {
      int i1 = query(2*p, l, (l+r)/2, i, j);
      int i2 = query(2*p+1, (l+r)/2+1, r, i, j);
      return min(i1, i2);
    }
  }

  int maxx(int p, int l, int r, int i, int j) {
    if (l > j || r < i) return 0;
    if (i <= l && r <= j) return mx[p];
    else {
      int i1 = maxx(2*p, l, (l+r)/2, i, j);
      int i2 = maxx(2*p+1, (l+r)/2+1, r, i, j);
      return max(i1, i2);
    }
  }
  
};

int N, M;
SegTree stT, stH;
v<int> t, h;
v<int> sig;

void initialize(std::vector<int> T, std::vector<int> H) {
  t = T;
  h = H;
  N = T.size();
  M = H.size();
  stT = SegTree(N);
  stH = SegTree(M);
  rep(i, 0, N) {
    stT.build(1, 0, N-1, i, T[i]);
  }
  rep(i, 0, M) {
    stH.build(1, 0, M-1, i, H[i]);
  }
  stack<int> s;
  stack<int> idx;
  sig.assign(N, -1);
  rep(i, 0, N) {
    while (s.size() && T[i] > s.top()) {
      sig[idx.top()] = i;
      idx.pop();
      s.pop();
    }
    s.push(T[i]);
    idx.push(i);
  }
  return;
}

bool salto_valido(int row1, int row2, int l, int r) {
  int mnH = stH.query(1, 0, M-1, l, r);
  int mnT = stT.query(1, 0, N-1, row1, row2);
  if (mnT > mnH) return true;
  else return false;
}

pair<int, int> find_range(int S) {
  int row = 0;
  int l, r;
  l = r = S;
  int lel = 0, rr = S;
  while (lel <= rr) {
    int m = (lel+rr)/2;
    if (stH.maxx(1, 0, M-1, m, r) < t[0]) {
      l = m;
      rr = m-1;
    }
    else lel = m+1;
  }
  lel = S;
  rr = M-1;
  while (lel <= rr) {
    int m = (lel+rr)/2;
    //cout << m << " " << stH.maxx(1, 0, M-1, l, m) << endl;
    if (stH.maxx(1, 0, M-1, l, m) < t[0]) {
      r = m;
      lel = m+1;
    }
    else rr = m-1;
  }
  while (sig[row] != -1 && salto_valido(row, sig[row], l, r)) {
    row = sig[row];
    lel = 0, rr = l;
    while (lel <= rr) {
      int m = (lel+rr)/2;
      if (stH.maxx(1, 0, M-1, m, r) < t[row]) {
        l = m;
        rr = m-1;
      }
      else lel = m+1;
    } 
    lel = r;
    rr = M-1;
    while (lel <= rr) {
      int m = (lel+rr)/2;
      if (stH.maxx(1, 0, M-1, l, m) < t[row]) {
        r = m;
        lel = m+1;
      }
      else rr = m-1;
    }
  }
  return {l, r};
}

bool can_reach(int L, int R, int S, int D) {
  int l1, r1;
  auto aux = find_range(S);
  l1 = aux.first, r1 = aux.second;
  int l2, r2;
  aux = find_range(D);
  l2 = aux.first, r2 = aux.second;
  //cout << l1 << " "<< r1 << " " << l2 << " "<< r2 << endl;
  if (l1 == l2 && r1 == r2) return true;
  else return false;
}

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