Submission #966672

#	Time	Username	Problem	Language	Result	Execution time	Memory
966672		kilkuwu	Strange Device (APIO19_strange_device)	C++17	100 / 100	469 ms	95604 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];
  }
  auto decompose = [&](int64_t t) -> std::pair<int64_t, int64_t> {
    return {t % B, t / B};
  };

  int step = (B + 1) % A;
  if (step == 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 = std::max(normalized.back().second, r);
      }
    }

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

  auto g = std::gcd(A, step);
  auto thres = A / g;

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

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

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

    if (qr >= thres) {
      segs.emplace_back(rl + ql * B, B - 1 + (thres - 1) * B);
      auto num_shift = qr / thres;
      qr -= num_shift * thres;
      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 = std::max(normalized.back().second, r);
    }
  }

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

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