Submission #1265044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265044		Kanon	Obstacles for a Llama (IOI25_obstacles)	C++20	100 / 100	334 ms	108888 KiB

obstacles

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

struct edge {
  int to;
  int val;
  edge(){
    to = INT_MAX;
    val = INT_MIN;
  };
  edge(int _to, int _val) : to(_to), val(_val) {};
};

void debug_out(edge e) {
  debug_out(make_pair(e.to, e.val));
}

void debug_out(vector<edge> e) {
  vector<pair<int, int>> ee;
  for (auto i : e) ee.push_back({i.to, i.val});
  debug_out(ee);
}

int Lg = 18;
vector<vector<edge>> toL;
vector<vector<edge>> toR;

void initialize(std::vector<int> T, std::vector<int> H) {
  T.push_back(0);
  int n = H.size();
  int N = T.size();
  vector<int> a(n);
  {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){return H[i] < H[j];});
    int pre = 0;
    for (int i : order) {
      a[i] = pre;
      while (a[i] < N && H[i] >= T[a[i]]) a[i]++;
      pre = a[i];
    }
  }

  SparseTable tab_T(T, [&](int i, int j){return min(i, j);});
  SparseTable tab_H(H, [&](int i, int j){return min(i, j);});
  auto height = [&](int i) {
    if (i >= 0 && i < n) return a[i];
    return N;
  };

  auto First_block = [&](int L, int R, int val, int side) {
    bool valid = tab_H.get(L, R) < val;
    if (!valid) return side == 1 ? -1 : n;
    while (R > L) {
      int mid = (L + R) / 2;
      bool LL = tab_H.get(L, mid) < val;
      bool RR = tab_H.get(mid + 1, R) < val;
      assert(LL || RR);
      if (!LL) L = mid + 1;
      else if (!RR) R = mid;
      else {
        if (side == 1) L = mid + 1;
        else R = mid;
      }
    }
    return R;
  };

  vector<edge> Lpar(n);
  vector<edge> Rpar(n);

  vector<int> que = {-1};
  for (int i = 0; i < n; i++) {
    while (que.size() && height(que.back()) <= height(i)) que.pop_back();
    if (que.size()) Lpar[i] = edge(que.back(), 0);
    que.push_back(i);
  }
  que = (vector<int>) {n};
  for (int i = n - 1; i >= 0; i--) {
    while (que.size() && height(que.back()) <= height(i)) que.pop_back();
    if (que.size()) Rpar[i] = edge(que.back(), 0);
    que.push_back(i);
  }

  {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){return a[i] > a[j];});
    for (int i : order) {
      int Lp = Lpar[i].to;
      if (Lp == INT_MAX) continue;
      int Rp = Rpar[i].to;
      assert(Rp != INT_MAX);
      int val = height(Rp) >= height(Lp) ? -1 : Lpar[Rp].val;
      int min_T = tab_T.get(height(i), min(height(Lp), height(Rp)) - 1);
      int nxt = First_block(Lp + 1, Rp - 1, min_T, -1);
      Lpar[i].val = max(nxt, val);
    }
    for (int i : order) {
      int Rp = Rpar[i].to;
      if (Rp == INT_MAX) continue;
      int Lp = Lpar[i].to;
      assert(Lp != INT_MAX);
      int val = height(Lp) >= height(Rp) ? n : Rpar[Lp].val;
      int min_T = tab_T.get(height(i), min(height(Lp), height(Rp)) - 1);
      int nxt = First_block(Lp + 1, Rp - 1, min_T, +1);
      Rpar[i].val = min(nxt, val);
    }
  }

  toL = vector<vector<edge>>(n, vector<edge>(Lg));
  toR = vector<vector<edge>>(n, vector<edge>(Lg));
  for (int i = 0; i < n; i++) {
    toL[i][0] = Lpar[i];
    toR[i][0] = Rpar[i];
  }
  for (int d = 1; d < Lg; d++) {
    for (int i = 0; i < n; i++) {
      int pL = toL[i][d - 1].to;
      int pR = toR[i][d - 1].to;
      if (0 <= pL && pL <= n - 1) {
        toL[i][d].to = toL[pL][d - 1].to;
        toL[i][d].val = max(toL[pL][d - 1].val, toL[i][d - 1].val);
      }
      if (0 <= pR && pR <= n - 1) {
        toR[i][d].to = toR[pR][d - 1].to;
        toR[i][d].val = min(toR[pR][d - 1].val, toR[i][d - 1].val);
      }
    }
  }
}

bool can_reach(int L, int R, int S, int D) {
  if (S > D) swap(S, D);
  if (S == D) return true;
  edge curS(S, 200000);
  for (int d = Lg - 1; d >= 0; d--) {
    int np = toR[curS.to][d].to;
    if (np == INT_MAX || np >= D) continue;
    curS.val = min(curS.val, toR[curS.to][d].val);
    curS.to = np;
  }
  if (curS.val < L) return false;
  edge curD(D, -1);
  for (int d = Lg - 1; d >= 0; d--) {
    int np = toL[curD.to][d].to;
    if (np == INT_MAX || np <= S) continue;
    curD.val = max(curD.val, toL[curD.to][d].val);
    curD.to = np;
  }
  if (curD.val > R) return false;
  return true;
}

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