제출 #966635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966635		kilkuwu	이상한 기계 (APIO19_strange_device)	C++17	5 / 100	379 ms	94524 KiB

strange_device

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

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

  int n;
  int64_t A, B;
  std::cin >> n >> A >> B;
  std::vector<int64_t> L(n), R(n);
  for (int i = 0; i < n; i++) {
    std::cin >> L[i] >> R[i];
  }

  if ((B + 1) % A == 0) {
    std::vector<std::pair<int64_t, int64_t>> segs;
    for (int i = 0; i < n; i++) {
      if (R[i] - L[i] + 1 < B) {
        auto r0 = L[i] % B;
        auto r1 = R[i] % B;
        if (r0 <= r1) {
          segs.emplace_back(r0, r1);
        } else {
          segs.emplace_back(0, r1);
          segs.emplace_back(r0, B - 1);
        }
      } else {
        segs.emplace_back(0, B - 1);
      }
    }

    std::sort(segs.begin(), segs.end());

    std::vector<std::pair<int64_t, int64_t>> normalized;
    for (auto [l, r] : segs) {
      if (normalized.empty() || l > normalized.back().second) {
        normalized.emplace_back(l, r);
      } else {
        normalized.back().second = r;
      }
    }

    int64_t ans = 0;
    for (auto [l, r] : normalized) {
      ans += r - l + 1;
    }
    std::cout << ans << nl;
    return 0;
  } 

  std::vector<std::pair<int64_t, int64_t>> segs;

  auto decompose = [&](int64_t t) -> std::pair<int64_t, int64_t> {
    return {t % B, t / B};
  };

  auto process = [&](int64_t l, int64_t r) {
    auto len = r - l + 1;
    if (len / B >= A) {
      segs.emplace_back(0, A * B - 1);
    }
    auto [rl, ql] = decompose(l);
    auto [rr, qr] = decompose(r);

    if (ql >= A) {
      auto num_shift = ql / A; 
      ql -= num_shift * A;
      qr -= num_shift * A;
    }

    if (qr >= A) {
      segs.emplace_back(rl + ql * B, B - 1 + (A - 1) * B);
      auto num_shift = qr / A;
      qr -= num_shift * A;
      segs.emplace_back(0, rr + qr * B);
    } else {
      segs.emplace_back(rl + ql * B, rr + qr * B);
    }
  };

  for (int i = 0; i < n; i++) {
    process(L[i], R[i]);
  }
  std::sort(segs.begin(), segs.end());

  std::vector<std::pair<int64_t, int64_t>> normalized;
  for (auto [l, r] : segs) {
    if (normalized.empty() || l > normalized.back().second) {
      normalized.emplace_back(l, r);
    } else {
      normalized.back().second = r;
    }
  }

  int64_t ans = 0;
  for (auto [l, r] : normalized) {
    ans += r - l + 1;
  }
  std::cout << ans << nl;
}

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