제출 #1361312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361312		edo	Fire (BOI24_fire)	C++20	100 / 100	103 ms	49008 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<pair<ll, ll>> seg;
  seg.reserve(n << 1);
  for (int i = 0; i < n; ++i) {
    ll s, e;
    cin >> s >> e;
    if (s > e)
      seg.emplace_back(s, e + m);
    else
      seg.emplace_back(s, e);
  }
  n = seg.size();
  for (int i = 0; i < n; ++i) {
    seg.emplace_back(seg[i].first + m, seg[i].second + m);
  }
  ranges::sort(seg);
  n = seg.size();
  vector<ll> l(n), r(n);
  vector<int> pref(n + 1), nxt(n);
  vector up(20, vector<int>(n));
  for (int i = 0; i < n; ++i)
    tie(l[i], r[i]) = seg[i];
  for (int i = 1; i < n; ++i)
    if (r[i] > r[pref[i - 1]])
      pref[i] = i;
    else
      pref[i] = pref[i - 1];

  for (int i = 0; i < n; ++i)
    nxt[i] = pref[upper_bound(l.begin(), l.end(), r[i]) - l.begin() - 1];

  up[0] = nxt;

  for (int lg = 1; lg < 20; ++lg)
    for (int i = 0; i < n; ++i)
      up[lg][i] = up[lg - 1][up[lg - 1][i]];

  ll ans = 1e12;
  for (int i = 0; i < n; ++i) {
    if (l[i] >= m)
      continue;
    ll target = l[i] + m, cnt = 1, cur = i;
    if (r[i] >= target) {
      ans = min(ans, cnt);
      continue;
    }

    for (int lg = 20; lg--;) {
      int to = up[lg][cur];
      if (r[to] < target) {
        cnt += (1 << lg);
        cur = to;
      }
    }
    cur = up[0][cur];
    cnt++;
    if (r[cur] >= target) {
      ans = min(ans, cnt);
    }
  }

  cout << (ans == 1e12 ? -1 : ans);

  return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 17 / 17
• 서브태스크 3: 9 / 9
• 서브태스크 4: 13 / 13
• 서브태스크 5: 21 / 21
• 서브태스크 6: 26 / 26