Submission #1255877

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

obstacles

#pragma GCC optimize("Ofast")
#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++)
#define cout if(0) cout

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 1e9;
    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;
v<v<int>> liftleft;
v<v<int>> liftright;
void initialize(std::vector<int> T, std::vector<int> H) {
  t = T;
  h = H;
  N = T.size();
  M = H.size();
  //rep(i, 0, N) {rep(j, 0, M) {if (T[i] > H[j]) cout << 1 << " ";else cout << 0 << " ";}cout << endl;}
  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]);
  }
  liftleft.assign(M, v<int>(20, 1e9));
  liftright.assign(M, v<int>(20, 1e9));
  rep(i, 0, M) {
    if (i > 0) liftleft[i][0] = H[i-1];
    if (i < M-1) liftright[i][0] = H[i+1];
  }
  rep(j, 1, 20) {
    rep(i, 0, M) {
      if (i - (1 << (j-1)) > 0) liftleft[i][j] = max(liftleft[i - (1 << (j-1))][j-1], liftleft[i][j-1]);
      if (i + (1 << (j-1)) < M) {
        if (j == 2 && i == 1) {
          cout << liftright[i+(1<<(j-1))][j-1] << " " << liftright[i][j-1] << endl;
        }
        liftright[i][j] = max(liftright[i + (1 << (j-1))][j-1], liftright[i][j-1]);
      }
    }
  }
  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;
  for (int i = 19; i >= 0; i--) {
    if (liftleft[l][i] < t[row]) {
      l -= (1 << i);
    }
  }
  for (int i = 19; i >= 0; i--) {
    if (liftright[r][i] < t[row]) {
      r += (1 << i);
    }
  }
  while (sig[row] != -1 && salto_valido(row, sig[row], l, r)) {
    row = sig[row];
    cout << l << " "<< r << endl;
    for (int i = 19; i >= 0; i--) {
      if (liftleft[l][i] < t[row]) {
        l -= (1 << i);
      }
    }
    for (int i = 19; i >= 0; i--) {
      cout << r << " " << i << " " << liftright[r][i] << endl;
      if (liftright[r][i] < t[row]) {
        r += (1 << i);
        cout << i << endl;
      }
    }
  }
  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: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17