Submission #1229361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229361		avighna	Event Hopping (BOI22_events)	C++20	0 / 100	161 ms	11060 KiB

events

#include <bits/stdc++.h>

int main() {
  int n, q;
  std::cin >> n >> q;
  struct time {
    int s, e;
  };
  std::vector<time> a(n);
  for (auto &[s, e] : a) {
    std::cin >> s >> e;
  }

  auto comp = [](time a, time b) {
    return a.s < b.s;
  };
  std::sort(a.begin(), a.end(), comp);
  std::vector<std::vector<int>> pref(n);
  pref[0] = {0};
  for (int i = 1; i < n; ++i) {
    pref[i] = pref[i - 1];
    pref[i].push_back(i);
    std::sort(pref[i].begin(), pref[i].end(), [&](int idx1, int idx2) {
      return a[idx1].e > a[idx2].e;
    });
    if (pref[i].size() > 2) {
      pref[i].pop_back();
    }
  }

  int tot_comps = 0, timer = 0;
  std::vector<int> comp_num(n), start(n);
  std::vector<bool> vis(n);
  auto dfs = [&](auto &&self, int u) {
    if (vis[u]) {
      return;
    }
    vis[u] = true;
    start[u] = timer++;
    time t = {a[u].e, 0};
    auto it = std::upper_bound(a.begin(), a.end(), t, comp);
    if (it == a.begin()) {
      comp_num[u] = tot_comps++;
      return;
    }
    --it;
    if (pref[it - a.begin()].empty()) {
      comp_num[u] = tot_comps++;
      return;
    }
    int idx = pref[it - a.begin()][0];
    if (u == idx) {
      if (pref[it - a.begin()].size() == 1) {
        comp_num[u] = tot_comps++;
        return;
      }
      idx = pref[it - a.begin()][1];
    }
    if (a[u].e > a[idx].e) {
      comp_num[u] = tot_comps++;
      return;
    }
    self(self, idx);
    comp_num[u] = comp_num[idx];
  };
  for (int i = 0; i < n; ++i) {
    dfs(dfs, i);
  }

  while (q--) {
    int beg, end;
    std::cin >> beg >> end;
    --beg, --end;
    if (comp_num[beg] != comp_num[end] or start[beg] > start[end]) {
      std::cout << "impossible\n";
    } else {
      std::cout << start[end] - start[beg] << '\n';
    }
  }
}

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