Submission #408732

#	Time	Username	Problem	Language	Result	Execution time	Memory
408732		Cyanmond	Strange Device (APIO19_strange_device)	C++17	100 / 100	1936 ms	99552 KiB

strange_device

#include "bits/stdc++.h"
#pragma region header
#define loop(n) for ([[maybe_unused]] size_t lpcnt_ = 0; lpcnt_ < (n); ++lpcnt_)
using i32 = int;
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using isize = ptrdiff_t;
using usize = size_t;
template <class T>
using Vec = std::vector<T>;
template <class T, size_t N>
using Arr = std::array<T, N>;

template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div;
constexpr i32 infi32 = infty<i32, 2>;  // 1073741823
constexpr u32 infu32 = infty<u32, 2>;  // 2147483647
constexpr i64 infi64 = infty<i64, 4>;  // 2305843009213693951
constexpr u64 infu64 = infty<u64, 4>;  // 4611686018427387903
// infi32 / 2 < 10^9
// infi64 / 2 < 2 * 10^18
constexpr char endl = '\n';  // std::endl without flush ('\n')
constexpr usize operator"" _uz(u64 v) { return usize(v); }

inline int popcount(unsigned long long x) {
#if __cplusplus >= 202002L
  return std::popcount(x);
#else
#ifdef __GNUC__
  return __builtin_popcount(x);
#else
  x = x - ((x >> 1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
  x = x + (x >> 8);
  x = x + (x >> 16);
  x = x + (x >> 32);
  return x & 0x0000007f;
#endif
#endif
}

template <class T>
constexpr bool setmin(T& a, const T b) noexcept {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
constexpr bool setmax(T& a, const T b) noexcept {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
constexpr T difrc(const T a, const T b) noexcept {
  return a > b ? a - b : b - a;
}

class range {
  using value_type = usize;
  struct range_iterator {
    value_type itr;
    constexpr range_iterator(const value_type pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr value_type operator*() const noexcept { return itr; }
  };
  const range_iterator first, last;

 public:
  constexpr range(const value_type first_, const value_type last_) noexcept
      : first(first_), last(last_) {}
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }
};

template <class T>
class span {
  using iterator_type = typename std::vector<T>::iterator;
  iterator_type first, last;

 public:
  span(std::vector<T>& v, const usize l, const usize r) noexcept
      : first(v.begin() + l), last(v.begin() + r) {}
  auto begin() const noexcept { return first; }
  auto end() const noexcept { return last; }
};

template <class F>
class rec_lambda {
  F f;

 public:
  explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};
#pragma endregion

void main_() {
  usize N;
  u64 A, B;
  std::cin >> N >> A >> B;
  u64 prd =
      (infu64 / (A / std::gcd(A, B + 1)) < B ? infu64
                                             : A / std::gcd(A, B + 1) * B);

  std::vector<u64> L(N), R(N);
  for (auto i : range(0, N)) std::cin >> L[i] >> R[i];

  std::map<u64, std::pair<u64, u64>> M;
  M[prd];  // construct
  for (usize i : range(0, N)) {
    if (++R[i] - L[i] >= prd) {
      std::cout << prd << '\n';
      return;
    }
    u64 l = L[i] % prd, r = R[i] % prd;
    ++M[l].first;
    ++M[r].second;
    if (l >= r) {
      ++M[prd].second;
      ++M[0].first;
    }
  }
  u64 cnt = 0, ans = 0, lst = 0;
  for (auto& [idx, pair] : M) {
    auto& [ps, ms] = pair;
    if (cnt != 0) ans += idx - lst;
    cnt += ps;
    cnt -= ms;
    lst = idx;
  }
  std::cout << ans << '\n';
  // code end
}

int main() { main_(); }

/*
 * task: APIO2019 A Strange Device
 * created: 19.05.2021
 */

Compilation message (stderr)

strange_device.cpp:2: warning: ignoring '#pragma region header' [-Wunknown-pragmas]
    2 | #pragma region header
      | 
strange_device.cpp:108: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  108 | #pragma endregion
      |

• 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