oj.uz

Submission #857812

# Submission time Handle Problem Language Result Execution time Memory
857812 2023-10-07T03:09:19 Z NeroZein Event Hopping (BOI22_events) C++17
30 / 100
 95 ms 14324 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int LOG = 18;
const int N = 1e5 + 5;

int s[N], e[N]; 
int nx[LOG][N]; 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q; 
  vector<pair<int, int>> ev;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i] >> e[i];
    ev.emplace_back(s[i], ~i);
    ev.emplace_back(e[i], i); 
  }
  sort(ev.begin(), ev.end()); 
  set<pair<int, int>> active;
  for (int i = 0; i < 2 * n; ++i) {
    auto [x, y] = ev[i];
    if (y < 0) {
      active.emplace(e[~y], ~y); 
    } else {
      active.erase({x, y});
      if (!active.empty()) {
        auto tmp = *active.rbegin(); 
        nx[0][y] = tmp.second;
      }
    }
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 1; i <= n; ++i) {
      nx[j][i] = nx[j - 1][nx[j - 1][i]]; 
    }
  }
  auto intersect = [&](int i, int j) -> bool {
    return s[j] <= e[i] && e[i] <= e[j];
  };
  while (q--) {
    int st, en;
    cin >> st >> en;
    if (st == en) {
      cout << 0 << '\n';
      continue;
    }
    if (intersect(st, en)) {
      cout << 1 << '\n';
      continue;
    }
    int ans = 0; 
    for (int j = LOG - 1; j >= 0; --j) {
      if (nx[j][st] && e[nx[j][st]] < s[en]) {
        st = nx[j][st]; 
        ans += 1 << j; 
      }
    }
    st = nx[0][st];
    if (intersect(st, en)) {
      cout << ans + 2 << '\n';
    } else {
      cout << "impossible" << '\n'; 
    }
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 57 ms 10408 KB Output is correct
3 Correct 63 ms 10436 KB Output is correct
4 Correct 74 ms 10484 KB Output is correct
5 Correct 65 ms 10436 KB Output is correct
6 Correct 64 ms 10440 KB Output is correct
7 Correct 64 ms 10628 KB Output is correct
8 Correct 53 ms 11044 KB Output is correct
9 Correct 50 ms 10696 KB Output is correct
10 Correct 73 ms 10880 KB Output is correct
11 Correct 70 ms 10880 KB Output is correct
12 Correct 42 ms 11036 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10396 KB Output is correct
2 Correct 63 ms 10504 KB Output is correct
3 Correct 72 ms 10444 KB Output is correct
4 Correct 58 ms 10692 KB Output is correct
5 Correct 69 ms 10816 KB Output is correct
6 Correct 77 ms 10488 KB Output is correct
7 Correct 95 ms 10740 KB Output is correct
8 Correct 69 ms 10788 KB Output is correct
9 Correct 58 ms 14324 KB Output is correct
10 Correct 65 ms 10112 KB Output is correct
11 Correct 66 ms 11208 KB Output is correct
12 Correct 64 ms 10184 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 57 ms 10408 KB Output is correct
3 Correct 63 ms 10436 KB Output is correct
4 Correct 74 ms 10484 KB Output is correct
5 Correct 65 ms 10436 KB Output is correct
6 Correct 64 ms 10440 KB Output is correct
7 Correct 64 ms 10628 KB Output is correct
8 Correct 53 ms 11044 KB Output is correct
9 Correct 50 ms 10696 KB Output is correct
10 Correct 73 ms 10880 KB Output is correct
11 Correct 70 ms 10880 KB Output is correct
12 Correct 42 ms 11036 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6632 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Incorrect 1 ms 6492 KB Output isn't correct
18 Halted 0 ms 0 KB -