Submission #1015845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015845		asdfgrace	Event Hopping (BOI22_events)	C++17	100 / 100	86 ms	31420 KiB

events

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

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
sort by right bound
out of everything with l[i] <= r[j] <= r[i]
with leftmost left bound
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&] (int x, int y) {
    return a[x][1] < a[y][1] || (a[x][1] == a[y][1] && a[x][0] < a[y][0]);
  });
  vector<int> at(n);
  for (int i = 0; i < n; i++) {
    at[ord[i]] = i;
  }
  sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) {
    return a1[1] < a2[1] || (a1[1] == a2[1] && a1[0] < a2[0]);
  });
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++) {
    l[i] = a[i][0];
    r[i] = a[i][1];
  }
  vector<vector<array<int, 2>>> rmq(20, vector<array<int, 2>>(n));
  for (int i = 0; i < n; i++) {
    rmq[0][i] = {l[i], i};
  }
  for (int j = 1; j < 20; j++) {
    for (int i = 0; i < n - (1 << (j - 1)); i++) {
      rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
    }
  }
  function<array<int, 2>(int, int)> mnq = [&] (int lb, int rb) {
    int len = rb - lb + 1, mxbit = 31 - __builtin_clz(len);
    return min(rmq[mxbit][lb], rmq[mxbit][rb - (1 << mxbit) + 1]);
  };
  vector<int> to(n);
  for (int i = 0; i < n; i++) {
    int lb = lower_bound(r.begin(), r.end(), l[i]) - r.begin();
    int rb = upper_bound(r.begin(), r.end(), r[i]) - r.begin() - 1;
    array<int, 2> best = mnq(lb, rb);
    to[i] = best[1];
  }
  vector<vector<int>> lift(20, vector<int>(n, 0));
  lift[0] = to;
  for (int j = 1; j < 20; j++) {
    for (int i = 0; i < n; i++) {
      lift[j][i] = lift[j - 1][lift[j - 1][i]];
    }
  }
  while (q--) {
    int st, en;
    cin >> st >> en;
    st--; en--;
    st = at[st]; en = at[en];
    if (r[en] < r[st]) {
      cout << "impossible\n";
      continue;
    } else if (st == en) {
      cout << 0 << '\n';
      continue;
    } else if (l[en] <= r[st]) {
      cout << 1 << '\n';
      continue;
    }
    int ans = 0;
    for (int bit = 19; bit >= 0; bit--) {
      if (l[lift[bit][en]] > r[st]) {
        ans += 1 << bit;
        en = lift[bit][en];
      }
    }
    en = to[en];
    ans++;
    if (l[en] > r[st]) {
      cout << "impossible\n";
    } else {
      cout << ans + 1 << '\n';
    }
  }
}

/*
any observations help

check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER

NEVER GIVE UP
*/

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