oj.uz

Submission #1015843

# Submission time Handle Problem Language Result Execution time Memory
1015843 2024-07-06T22:01:09 Z asdfgrace Event Hopping (BOI22_events) C++17
20 / 100
 90 ms 31296 KB 
#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;
    }
    int ans = 0;
    for (int bit = 19; bit >= 0; bit--) {
      if (r[lift[bit][en]] > r[st]) {
        ans += 1 << bit;
        en = lift[bit][en];
      }
    }
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 67 ms 30640 KB Output is correct
3 Correct 63 ms 30768 KB Output is correct
4 Correct 70 ms 30804 KB Output is correct
5 Correct 88 ms 30784 KB Output is correct
6 Correct 69 ms 30788 KB Output is correct
7 Correct 71 ms 30788 KB Output is correct
8 Incorrect 67 ms 31176 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30784 KB Output is correct
2 Correct 69 ms 30652 KB Output is correct
3 Correct 72 ms 30812 KB Output is correct
4 Correct 68 ms 31296 KB Output is correct
5 Correct 76 ms 31172 KB Output is correct
6 Correct 83 ms 30788 KB Output is correct
7 Correct 82 ms 30788 KB Output is correct
8 Correct 90 ms 30924 KB Output is correct
9 Correct 54 ms 28904 KB Output is correct
10 Correct 66 ms 30516 KB Output is correct
11 Correct 64 ms 30276 KB Output is correct
12 Correct 72 ms 30532 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 67 ms 30640 KB Output is correct
3 Correct 63 ms 30768 KB Output is correct
4 Correct 70 ms 30804 KB Output is correct
5 Correct 88 ms 30784 KB Output is correct
6 Correct 69 ms 30788 KB Output is correct
7 Correct 71 ms 30788 KB Output is correct
8 Incorrect 67 ms 31176 KB Output isn't correct
9 Halted 0 ms 0 KB -