Submission #844813

#	Time	Username	Problem	Language	Result	Execution time	Memory
844813		obokaman	Event Hopping (BOI22_events)	C++17	100 / 100	269 ms	14256 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);
  vector<int> anc(17 * 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 < N; ++i) {
    anc[i] = parent[i];
  }
  for (int lev = 1; lev < 17; ++lev) {
    for (int i = 0; i < N; ++i) {
      anc[lev * N + i] = anc[(lev - 1) * N + anc[(lev - 1) * N + i]];
    }
  }

  //  for (int lev = 0; lev < 17; ++lev) {
  //   for (int i = 0; i < N; ++i) {
  //     cout << " " << anc[lev * N + i];
  //   }
  //   cout << endl;
  // }
  // cout << 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 = 0;
      for (int l = 16; l >= 0; --l) {
        //        cout << x << ": ";
        int x2 = anc[l * N + x];
        if (ints[s].second < ints[x2].first) {
          // x guaranteed to never contain s.
          x = x2;
          steps += (1 << l);
        }
        // cout << x << "... ";
      }
      //      cout << endl;
      if (parent[x] != x) {
        // 1 extra step possible
        cout << (steps + 2) << endl;
      } else {
        cout << "impossible" << endl;
      }
    }
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30