제출 #249114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249114		KoD	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	1910 ms	298804 KiB

strange_device

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <map>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}

struct range {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_) noexcept : i(i_) { }
    constexpr void operator ++ () noexcept { ++i; }
    constexpr itr operator * () const noexcept { return i; }
    constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
  };
  const iterator l, r;
  constexpr range(itr l_, itr r_) noexcept : l(l_), r(std::max(l_, r_)) { }
  constexpr iterator begin() const noexcept { return l; }
  constexpr iterator end() const noexcept { return r; }
};

struct revrange {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_) noexcept : i(i_) { }
    constexpr void operator ++ () noexcept { --i; }
    constexpr itr operator * () const noexcept { return i; }
    constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
  };
  const iterator l, r;
  constexpr revrange(itr l_, itr r_) noexcept : l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr iterator begin() const noexcept { return r; }
  constexpr iterator end() const noexcept { return l; }
};

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

std::vector<std::pair<i64, i64>> resolve_overlapping(std::vector<std::pair<i64, i64>> vec) {
  std::sort(vec.begin(), vec.end());
  i64 L = -1, R = -1;
  std::vector<std::pair<i64, i64>> res;
  for (auto [l, r]: vec) {
    if (R < l) {
      if (L != -1 && R != -1) {
        res.emplace_back(L, R);
      }
      L = l;
      R = r;
    }
    else {
      chmax(R, r);
    }
  }
  if (L != -1 && R != -1) {
    res.emplace_back(L, R);
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  size_t N;
  i64 A, B;
  std::cin >> N >> A >> B;
  i64 C = (B % A) + 1;
  i64 D = A / std::gcd(A, C);
  std::vector<std::pair<i64, i64>> intervals;
  intervals.reserve(N);
  __int128_t loop = __int128_t(B) * __int128_t(D);
  while (N--) {
    i64 l, r;
    std::cin >> l >> r;
    i64 sl = l / loop;
    i64 sr = r / loop;
    switch (sr - sl) {
    case 0:
      intervals.emplace_back(l % loop, r % loop);
    break;
    case 1:
      intervals.emplace_back(l % loop, loop - 1);
      intervals.emplace_back(0, r % loop);
    break;
    default:
      std::cout << (i64) loop << '\n';
      return 0;
    break;
    }
  }
  intervals = resolve_overlapping(intervals);
  std::vector<std::pair<i64, i64>> covered;
  std::map<i64, std::vector<std::pair<i64, i64>>> fragments;
  for (auto [l, r]: intervals) {
    i64 sl = l / B;
    i64 sr = r / B;
    switch (sr - sl) {
    case 0:
      fragments[sl].emplace_back(l % B, r % B);
    break;
    case 1:
      fragments[sl].emplace_back(l % B, B - 1);
      fragments[sr].emplace_back(0, r % B);
    break;
    default:
      covered.emplace_back(sl + 1, sr - 1);
      fragments[sl].emplace_back(l % B, B - 1);
      fragments[sr].emplace_back(0, r % B);
    break;
    }
  }
  covered = resolve_overlapping(covered);
  i64 ans = 0, cover = 0;
  for (auto [k, vec]: fragments) {
    auto itr = std::upper_bound(covered.begin(), covered.end(), std::make_pair(k, i64(-1)));
    if (itr != covered.begin()) {
      itr = std::prev(itr);
      if (itr -> second >= k) {
        --cover;
        continue;
      }
    }
    vec = resolve_overlapping(vec);
    for (auto [l, r]: vec) {
      ans += r - l + 1;
    }
  }
  for (auto [l, r]: covered) {
    cover += r - l + 1;
  }
  std::cout << ans + B * cover << '\n';
  return 0;
}

• 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