Submission #1113303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113303		flashmt	Event Hopping (BOI22_events)	C++17	100 / 100	236 ms	52736 KiB

events

#include <bits/stdc++.h>
using namespace std;
 
template<typename T>
struct SparseTable
{
  int n;
  vector<vector<T>> mat;
 
  SparseTable(const vector<T>& a)
  {
    n = int(a.size());
    int maxLog = 32 - __builtin_clz(n);
    mat.resize(maxLog);
    mat[0] = a;
    for (int j = 1; j < maxLog; j++)
    {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++)
        mat[j][i] = min(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
    }
  }
 
  T get(int from, int to)
  {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 31 - __builtin_clz(to - from + 1);
    return min(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};
 
const int oo = 27081993;
const int LG = 17;
 
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<pair<int, int>> a;
  map<int, int> values;
  for (int i = 0; i < n; i++)
  {
    int l, r;
    cin >> l >> r;
    a.push_back({l, r});
    values[l] = values[r] = 0;
  }
 
  int valueCnt = 0;
  for (auto [k, _] : values)
    values[k] = valueCnt++;
 
  vector<pair<int, int>> minL(valueCnt, make_pair(oo, -1));
  for (int i = 0; i < n; i++)
  {
    auto [l, r] = a[i];
    l = values[l];
    r = values[r];
    a[i] = {l, r};
    minL[r] = min(minL[r], make_pair(l, i));
  }
 
  SparseTable<pair<int, int>> st(minL);
  vector<vector<int>> prev(n, vector<int>(LG, -1));
  for (int i = 0; i < n; i++)
  {
    auto [l, id] = st.get(a[i].first, a[i].second);
    if (l < a[i].first)
      prev[i][0] = id;
  }
  for (int j = 0; j + 1 < LG; j++)
    for (int i = 0; i < n; i++)
      if (prev[i][j] >= 0)
        prev[i][j + 1] = prev[prev[i][j]][j];
 
  while (q--)
  {
    int s, t;
    cin >> s >> t;
    s--; t--;
    if (s == t) cout << "0\n";
    else if (a[t].first <= a[s].second && a[s].second <= a[t].second) cout << "1\n";
    else if (a[s].second > a[t].second) cout << "impossible\n";
    else
    {
      int ans = 1;
      for (int i = LG - 1; i >= 0; i--)
        if (prev[t][i] >= 0 && a[prev[t][i]].first > a[s].second)
        {
          ans += 1 << i;
          t = prev[t][i];
        }
 
      if (prev[t][0] >= 0 && a[prev[t][0]].first <= a[s].second) ans++;
      else ans = -1;
 
      if (ans < 0) cout << "impossible\n";
      else cout << ans << '\n';
    }
  }
}

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