Submission #1166920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166920		fryingduc	Event Hopping (BOI22_events)	C++20	0 / 100	163 ms	21460 KiB

events

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
const int LG = 19;
int n, q;
int sl[maxn], sr[maxn];
int ord[maxn];
vector<int> ev[maxn];
int up[maxn][LG + 1];

void solve() {
  cin >> n >> q;
  vector<int> cprs;
  for (int i = 1; i <= n; ++i) {
    cin >> sl[i] >> sr[i];
    cprs.push_back(sl[i]);
    cprs.push_back(sr[i]);
    cprs.push_back(sl[i] - 1);
  }
  sort(cprs.begin(), cprs.end());
  cprs.erase(unique(cprs.begin(), cprs.end()), cprs.end());
  for (int i = 1; i <= n; ++i) {
    int d = lower_bound(cprs.begin(), cprs.end(), sl[i] - 1) - cprs.begin() + 1;
    sl[i] = lower_bound(cprs.begin(), cprs.end(), sl[i]) - cprs.begin() + 1;
    sr[i] = lower_bound(cprs.begin(), cprs.end(), sr[i]) - cprs.begin() + 1;
    ev[sr[i]].push_back(i);
    if (d > 1) ev[d - 1].push_back(-i);
  }
  set<pair<int, int>> s;
  for (int i = (int)cprs.size(); i; --i) {
    if (ev[i].empty()) continue;
    sort(ev[i].begin(), ev[i].end());
    for (auto j : ev[i]) {
      if (j < 0) {
        j = -j;
        s.erase(s.find(make_pair(sr[j], j)));
      } else {
        s.insert(make_pair(sr[j], j));
      }
    }
    for (auto j : ev[i]) {
      if (j > 0) {
        if (!s.empty()) {
          auto it = s.rbegin();
          if (j != it->second) {
            up[j][0] = it->second;
          }
        }
      }
    }
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }
  while (q--) {
    int s, e; cin >> s >> e;
    if (s == e) {
      cout << 0 << '\n';
      continue;
    }
    if (sr[e] < sr[s]) {
      cout << "impossible\n";
      continue;
    }
    int ans = 0;
    int cur = s;
    for (int i = LG; i >= 0; --i) {
      if (up[cur][i] and sr[up[cur][i]] < sr[e]) {
        ans ^= (1 << i);
        cur = up[cur][i];
      }
    }
    if (sl[e] <= sr[cur]) cout << ans + 1 << '\n';
    else {
//      debug(cur, up[cur][0]);
      cur = up[cur][0];
      if (!cur || sr[cur] > sr[e]) cout << "impossible\n";
      else cout << ans + 2 << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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