Submission #1007108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007108		MilosMilutinovic	Fire (BOI24_fire)	C++14	100 / 100	152 ms	38648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    if (a[i] > b[i]) {
      b[i] += m;
    }
  }
  vector<pair<int, int>> ev;
  for (int i = 0; i < n; i++) {
    ev.emplace_back(a[i], ~i);
    ev.emplace_back(b[i], i);
  }
  sort(ev.begin(), ev.end());
  set<pair<int, int>> st;
  const int L = 20;
  vector<vector<int>> jump(n, vector<int>(L));
  for (auto& p : ev) {
    int i = p.second;
    if (i >= 0) {
      jump[i][0] = prev(st.end())->second;
      st.erase({b[i], i});
    } else {
      i = ~i;
      st.insert({b[i], i});
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      jump[i][j] = jump[jump[i][j - 1]][j - 1];
    }
  }
  int res = n + 1;
  for (int i = 0; i < n; i++) {
    int idx = i;
    int total = 1;
    for (int j = L - 1; j >= 0; j--) {
      if (b[jump[idx][j]] < a[i] + m) {
        idx = jump[idx][j];
        total += (1 << j);
      }
    }
    res = min(res, total + 1);
  }
  if (res > n) {      
    cout << -1 << '\n';
  } else {
    cout << res << '\n';
  }
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26