oj.uz

Submission #689976

# Submission time Handle Problem Language Result Execution time Memory
689976 2023-01-30T00:09:45 Z bdl Event Hopping (BOI22_events) C++17
20 / 100
 137 ms 16796 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <array>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5, N_ = 1 << 18, L = 17;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, q;
  cin >> n >> q;
  static int l[N], r[N], c[N * 2];
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    c[i << 1 | 0] = l[i], c[i << 1 | 1] = r[i];
  }
  sort(c, c + n * 2);
  int m = unique(c, c + n * 2) - c;
  static array<int, 2> t[N_ * 2];
  int n_;
  n_ = 1;
  while (n_ < m)
    n_ <<= 1;
  for (int i = 1; i < n_ * 2; i++)
    t[i] = {N_, -1};
  for (int i = 0; i < n; i++) {
    l[i] = lower_bound(c, c + m, l[i]) - c;
    r[i] = lower_bound(c, c + m, r[i]) - c;
    int p = n_ + r[i];
    while (p > 0)
      t[p] = min(t[p], {l[i], i}), p >>= 1;
  }
  static int p[L][N];
  for (int i = 0; i < n; i++) {
    array<int, 2> x = {N_, -1};
    for (int l_ = l[i] + n_, r_ = r[i] + n_; l_ <= r_; l_ >>= 1, r_ >>= 1) {
      if ((l_ & 1) == 1)
        x = min(x, t[l_++]);
      if ((r_ & 1) == 0)
        x = min(x, t[r_--]);
    }
    p[0][i] = x[1];
  }
  for (int lg = 1; lg < L; lg++)
    for (int i = 0; i < n; i++)
      p[lg][i] = p[lg - 1][p[lg - 1][i]];
  while (q--) {
    int i, j;
    cin >> i >> j, i--, j--;
    if (r[j] < r[i]) {
      cout << "impossible\n";
      continue;
    }
    if (i == j) {
      cout << 0 << '\n';
      continue;
    }
    int k = 0;
    for (int lg = L - 1; lg >= 0; lg--)
      if (r[p[lg][j]] > r[i])
        k += 1 << lg, j = p[lg][j];
    if (k > n) {
      cout << "impossible\n";
      continue;
    }
    cout << k + 1 << '\n';
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 86 ms 14284 KB Output is correct
3 Correct 102 ms 14224 KB Output is correct
4 Correct 137 ms 14276 KB Output is correct
5 Correct 110 ms 14272 KB Output is correct
6 Correct 107 ms 14324 KB Output is correct
7 Correct 108 ms 14384 KB Output is correct
8 Incorrect 113 ms 16732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 1 ms 468 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 89 ms 14284 KB Output is correct
2 Correct 107 ms 14236 KB Output is correct
3 Correct 121 ms 14252 KB Output is correct
4 Correct 116 ms 16796 KB Output is correct
5 Correct 102 ms 14544 KB Output is correct
6 Correct 113 ms 16416 KB Output is correct
7 Correct 111 ms 16416 KB Output is correct
8 Correct 107 ms 16588 KB Output is correct
9 Correct 90 ms 14540 KB Output is correct
10 Correct 107 ms 16020 KB Output is correct
11 Correct 110 ms 15892 KB Output is correct
12 Correct 114 ms 16076 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 86 ms 14284 KB Output is correct
3 Correct 102 ms 14224 KB Output is correct
4 Correct 137 ms 14276 KB Output is correct
5 Correct 110 ms 14272 KB Output is correct
6 Correct 107 ms 14324 KB Output is correct
7 Correct 108 ms 14384 KB Output is correct
8 Incorrect 113 ms 16732 KB Output isn't correct
9 Halted 0 ms 0 KB -