oj.uz

Submission #720720

# Submission time Handle Problem Language Result Execution time Memory
720720 2023-04-09T06:08:33 Z NeroZein Event Hopping (BOI22_events) C++17
30 / 100
 268 ms 23868 KB 
#include <bits/stdc++.h>
using namespace std;

const int Log = 18; 
const int N = 100005;

int up[N][Log];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  map<int, int> mp; 
  vector<int> l(n + 1), r(n + 1); 
  vector<array<int, 3>> pts(n * 2); //L / R, idx, 0 / 1
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
    pts[(i - 1) * 2] = {l[i], 0, i};
    pts[(i - 1) * 2 + 1] = {r[i], 1, i};
    mp[l[i]]; mp[r[i]]; 
  }
  int idd = 0; 
  for (auto& it : mp) {
    it.second = ++idd; 
  }
  for (int i = 0; i < n * 2; ++i) {
    pts[i][0] = mp[pts[i][0]];
  }
  sort(pts.begin(), pts.end(), [&](array<int, 3> x, array<int, 3> y) {
    return x[0] == y[0] ? x[1] < y[1] : x[0] < y[0];
  });
  // for (int i = 0; i < n * 2; ++i) {
  //   cout << pts[i][0] << ' ' << pts[i][1] << ' ' << pts[i][2] << '\n';
  // }
  int mx = 0; 
  for (int i = 0; i < n * 2; ++i) {
    if (pts[i][1] == 0) {//isL
      mx = (r[pts[i][2]] > r[mx] ? pts[i][2] : mx);
    } else {//isR
      up[pts[i][2]][0] = mx;
    }
  }
  // for (int i = 1; i <= n; ++i) {
  //   cout << up[i][0] << ' ';
  // }
  for (int i = 1; i < Log; ++i) {
    for (int j = 1; j <= n; ++j) {
      up[j][i] = up[up[j][i - 1]][i - 1];
      assert(up[j][i] != 0);
    }
  }
  auto intersect = [&]( int y, int i, int j) -> bool {
    return y >= i && y <= j;
  };
  while (q--) {
    int u, v;
    cin >> u >> v;
    if (u == v) {
      cout << 0 << '\n';
      continue;
    }
    if (intersect(r[u], l[v], r[v])) {
      cout << 1 << '\n';
      continue;
    }
    int ans = 0; 
    for (int i = Log - 1; i >= 0; --i) {
      if (r[up[u][i]] < l[v]) {
        ans += 1 << i; 
        u = up[u][i]; 
      }
    }
    ans++;
    u = up[u][0]; 
    if (!intersect(r[u], l[v], r[v])) {
      cout << "impossible" << '\n';
    } else {
      cout << ans + 1 << '\n';
    }
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 174 ms 15780 KB Output is correct
3 Correct 162 ms 15728 KB Output is correct
4 Correct 193 ms 15776 KB Output is correct
5 Correct 164 ms 16232 KB Output is correct
6 Correct 164 ms 16716 KB Output is correct
7 Correct 176 ms 16864 KB Output is correct
8 Correct 201 ms 20888 KB Output is correct
9 Correct 202 ms 20988 KB Output is correct
10 Correct 180 ms 16072 KB Output is correct
11 Correct 187 ms 18124 KB Output is correct
12 Correct 102 ms 18636 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 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 167 ms 15756 KB Output is correct
2 Correct 190 ms 15756 KB Output is correct
3 Correct 187 ms 15768 KB Output is correct
4 Correct 218 ms 20992 KB Output is correct
5 Correct 199 ms 16076 KB Output is correct
6 Correct 267 ms 20556 KB Output is correct
7 Correct 259 ms 23608 KB Output is correct
8 Correct 224 ms 23868 KB Output is correct
9 Correct 191 ms 21820 KB Output is correct
10 Correct 238 ms 23324 KB Output is correct
11 Correct 268 ms 23072 KB Output is correct
12 Correct 243 ms 23500 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 174 ms 15780 KB Output is correct
3 Correct 162 ms 15728 KB Output is correct
4 Correct 193 ms 15776 KB Output is correct
5 Correct 164 ms 16232 KB Output is correct
6 Correct 164 ms 16716 KB Output is correct
7 Correct 176 ms 16864 KB Output is correct
8 Correct 201 ms 20888 KB Output is correct
9 Correct 202 ms 20988 KB Output is correct
10 Correct 180 ms 16072 KB Output is correct
11 Correct 187 ms 18124 KB Output is correct
12 Correct 102 ms 18636 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -