Submission #857833

#	Time	Username	Problem	Language	Result	Execution time	Memory
857833		NeroZein	Event Hopping (BOI22_events)	C++17	100 / 100	116 ms	16488 KiB

events

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int LOG = 18;
const int N = 1e5 + 5;

int l[N], r[N];
int nx[LOG][N]; 

template<typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
  int n;
  F func;
  vector<vector<T>> mat; 
  SparseTable(const vector<int>& a, F f) : func(f) {
    n = (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 query(int from, int to) {
    assert(0 <= from && from <= to && to <= n - 1); 
    int lg = 31 - __builtin_clz(to - from + 1);
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]); 
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
  }
  vector<int> id(n);
  iota(id.begin(), id.end(), 1); 
  sort(id.begin(), id.end(), [&](int i, int j) {
    return r[i] < r[j]; 
  });
  SparseTable<int> spa(id, [&](int i, int j) {
    return l[i] < l[j] ? i : j;
  }); 
  for (int i = 1; i <= n; ++i) {
    int lo = 0, hi = n;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (r[id[mid]] >= l[i]) {
        hi = mid;
      } else {
        lo = mid + 1; 
      }
    }
    int lo2 = -1, hi2 = n - 1;
    while (lo2 < hi2) {
      int mid = (lo2 + hi2 + 1) / 2;
      if (r[id[mid]] <= r[i]) {
        lo2 = mid;
      } else {
        hi2 = mid - 1; 
      }
    }
    if (lo2 == -1 || lo == n) {
      continue;
    }
    int tnx = spa.query(lo, lo2); 
    nx[0][i] = (tnx == i ? 0 : tnx); 
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 1; i <= n; ++i) {
      nx[j][i] = nx[j - 1][nx[j - 1][i]]; 
    }
  }
  while (q--) {
    int st, en;
    cin >> st >> en; 
    if (st == en) {
      cout << 0 << '\n';
      continue;
    }
    if (r[en] >= r[st] && l[en] <= r[st]) {
      cout << 1 << '\n';
      continue;
    } 
    int ans = 0;
    for (int j = LOG - 1; j >= 0; --j) {
      if (l[nx[j][en]] > r[st]) {
        en = nx[j][en];
        ans += 1 << j; 
      }
    }
    if (l[en] > r[st] && nx[0][en]) {
      cout << ans + 2 << '\n';
    } else {
      cout << "impossible" << '\n';
    }
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30