Submission #1166922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166922		fryingduc	Event Hopping (BOI22_events)	C++20	100 / 100	161 ms	20796 KiB

events

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
const int LG = 19;
int n, q;
int sl[maxn], sr[maxn];
int ord[maxn];
int up[maxn][LG + 1];

pair<int, int> tree[maxn << 2];
int lim;
void update(int pos, pair<int, int> val, int ind = 1, int l = 1, int r = lim) {
  if (l == r) {
    tree[ind] = min(tree[ind], val);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) update(pos, val, ind << 1, l, mid);
  else update(pos, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
}

pair<int, int> get(int x, int y, int ind = 1, int l = 1, int r = lim) {
  if (l > y || r < x) return make_pair(1e9, 1e9);
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return min(get(x, y, ind << 1, l, mid), get(x, y, ind << 1 | 1, mid + 1, r));
}

void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> sl[i] >> sr[i];
  }
  vector<int> cprs;
  for (int i = 1; i <= n; ++i) {
    cprs.push_back(sl[i]);
    cprs.push_back(sr[i]);
    cprs.push_back(sl[i] - 1);
  }
  sort(cprs.begin(), cprs.end());
  cprs.erase(unique(cprs.begin(), cprs.end()), cprs.end());
  lim = (int)cprs.size();
  memset(tree, 0x3f, sizeof(tree));
  for (int i = 1; i <= n; ++i) {
    int l = lower_bound(cprs.begin(), cprs.end(), sl[i]) - cprs.begin() + 1;
    int r = lower_bound(cprs.begin(), cprs.end(), sr[i]) - cprs.begin() + 1;
    update(r, make_pair(sl[i], i));
  }
  for (int i = 1; i <= n; ++i) {
    int l = lower_bound(cprs.begin(), cprs.end(), sl[i]) - cprs.begin() + 1;
    int r = lower_bound(cprs.begin(), cprs.end(), sr[i]) - cprs.begin() + 1;
    up[i][0] = get(l, r).second;
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }
  while (q--) {
    int s, e; cin >> s >> e;
    if (s == e) {
      cout << 0 << '\n';
      continue;
    }
    if (sr[e] < sr[s]) {
      cout << "impossible\n";
      continue;
    }
    if (sr[s] <= sr[e] and sr[s] >= sl[e]) {
      cout << 1 << '\n';
      continue;
    }
    int ans = 0;
    int cur = e;
    for (int i = LG; i >= 0; --i) {
      if (up[cur][i] and sl[up[cur][i]] > sr[s]) {
        ans ^= (1 << i);
        cur = up[cur][i];
      }
    }
    cur = up[cur][0];
    ++ans;
    if (sl[cur] > sr[s] || sr[cur] < sr[s]) {
      cout << "impossible\n";
      continue;
    }
    cout << ans + (sr[s] >= sl[cur]) << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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