oj.uz

Submission #689977

# Submission time Handle Problem Language Result Execution time Memory
689977 2023-01-30T00:24:41 Z bdl Event Hopping (BOI22_events) C++17
20 / 100
 146 ms 13656 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;
    }
    if (l[j] <= l[i] && r[j] >= r[i]) {
      cout << 1 << '\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 0 ms 340 KB Output is correct
2 Correct 85 ms 11104 KB Output is correct
3 Correct 106 ms 11192 KB Output is correct
4 Correct 128 ms 11100 KB Output is correct
5 Correct 105 ms 11240 KB Output is correct
6 Correct 109 ms 11172 KB Output is correct
7 Correct 112 ms 11256 KB Output is correct
8 Incorrect 116 ms 13656 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 0 ms 340 KB Output is correct
3 Correct 1 ms 468 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 0 ms 340 KB Output is correct
3 Correct 1 ms 468 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 0 ms 340 KB Output is correct
3 Correct 1 ms 468 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 92 ms 11160 KB Output is correct
2 Correct 105 ms 11156 KB Output is correct
3 Correct 146 ms 11060 KB Output is correct
4 Correct 116 ms 13652 KB Output is correct
5 Correct 103 ms 11504 KB Output is correct
6 Correct 120 ms 13332 KB Output is correct
7 Correct 124 ms 13328 KB Output is correct
8 Correct 111 ms 13396 KB Output is correct
9 Correct 86 ms 12508 KB Output is correct
10 Correct 118 ms 13012 KB Output is correct
11 Correct 113 ms 12752 KB Output is correct
12 Correct 126 ms 12912 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 85 ms 11104 KB Output is correct
3 Correct 106 ms 11192 KB Output is correct
4 Correct 128 ms 11100 KB Output is correct
5 Correct 105 ms 11240 KB Output is correct
6 Correct 109 ms 11172 KB Output is correct
7 Correct 112 ms 11256 KB Output is correct
8 Incorrect 116 ms 13656 KB Output isn't correct
9 Halted 0 ms 0 KB -