oj.uz

Submission #844802

# Submission time Handle Problem Language Result Execution time Memory
844802 2023-09-06T01:12:59 Z obokaman Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 4948 KB 
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<PII> ints(N);
  for (int i = 0; i < N; ++i) {
    cin >> ints[i].first >> ints[i].second;
  }
  vector<PII> sweep(2 * N);
  for (int i = 0; i < N; ++i) {
    sweep[2 * i] = {ints[i].first, i};
    // We need all closing to appear after all opening.
    sweep[2 * i + 1] = {ints[i].second, N + i};
  }
  sort(sweep.begin(), sweep.end());

  vector<int> parent(N);
  // {closing pos, index}, sorted decreasing closing pos. In addition, we
  // only keep those candidates that are useful: the ones that have smallest
  // open positions are allowed to have largest closing pos.
  vector<PII> candidates;
  for (int i = 2 * N - 1; i >= 0; --i) {
    auto& p = sweep[i];
    bool close = p.second >= N;
    int x = p.second % N;  // index

    if (close) {  // [?, ints[x].second]
      //      cout << "[?, " << ints[x].second << "]" << endl;
      // remove useless candidate, add new candidate
      while (!candidates.empty()) {
        auto& c = candidates.back();
        if (ints[x].first <= ints[c.second].first) {
          candidates.pop_back();
        } else {
          break;
        }
      }
      if (candidates.empty() ||
          ints[x].second < ints[candidates.back().second].second) {
        candidates.emplace_back(ints[x].second, x);
      }
      // //      cout << "candidates: ";
      // for (auto& c : candidates) {
      //   cout << c.first << "," << c.second << " ";
      // }
      // cout << endl;
    } else {  // [ints[x].first, ?]
      //      cout << "[" << ints[x].first << ",?]" << endl;
      // We compute x's parent: the candidate with largest second, but
      // smaller or equal than x's second.

      // (careful: we are using greater; also, since we will never match,
      // we don't care whether to use upper_bound or lower_bound). This
      // returns the left-most valid candidate, or .end() if it does not exist.
      auto it = upper_bound(candidates.begin(), candidates.end(),
                            PII{ints[x].second + 1, -1}, greater<PII>());
      if (it == candidates.end()) {
        parent[x] = x;  // all are invalid
      } else {
        //        cout << "Trobat it: " << it->first << "," << it->second <<
        //        endl;
        parent[x] = it->second;
      }
    }
  }
  // for (int i = 0; i < N; ++i) {
  //   cout << "parent " << i << ": " << parent[i] << endl;
  // }
  for (int i = 0; i < Q; ++i) {
    int s, e;
    cin >> s >> e;
    --s;
    --e;
    if (s == e) {
      cout << 0 << endl;
    } else if (ints[e].first <= ints[s].second &&
               ints[s].second <= ints[e].second) {
      cout << 1 << endl;
    } else if (ints[s].second > ints[e].second) {
      cout << "impossible" << endl;
    } else {
      int x = e;
      int steps = 1;
      while (ints[s].second < ints[x].first && x != parent[x]) {
        ++steps;
        x = parent[x];
      }
      if (ints[s].second >= ints[x].first) {
        cout << steps << endl;
      } else {
        cout << "impossible" << endl;
      }
    }
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1588 ms 3412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 432 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 444 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 613 ms 1876 KB Output is correct
20 Execution timed out 1550 ms 2000 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
15.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 169 ms 4920 KB Output is correct
20 Correct 74 ms 4324 KB Output is correct
21 Correct 78 ms 4880 KB Output is correct
22 Correct 73 ms 4944 KB Output is correct
23 Correct 69 ms 4948 KB Output is correct
24 Correct 73 ms 4916 KB Output is correct
25 Correct 50 ms 4432 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1536 ms 3252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1588 ms 3412 KB Time limit exceeded
3 Halted 0 ms 0 KB -