제출 #844791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844791		obokaman	Event Hopping (BOI22_events)	C++17	0 / 100	1586 ms	5340 KiB

events

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30