oj.uz

Submission #844791

# Submission time Handle Problem Language Result Execution time Memory
844791 2023-09-06T00:40:06 Z obokaman Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 5340 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 first invalid candidate.
      auto it = upper_bound(candidates.begin(), candidates.end(),
                            PII{ints[x].first - 1, N + 1}, greater<PII>());
      if (it == candidates.begin()) {
        parent[x] = x;  // all are invalid
      } else {
        --it;
        //        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 0 ms 604 KB Output is correct
2 Execution timed out 1586 ms 5340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 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 348 KB Output is correct
6 Incorrect 1 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 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 348 KB Output is correct
6 Incorrect 1 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 436 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 348 KB Output is correct
6 Incorrect 1 ms 448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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