oj.uz

Submission #408732

# Submission time Handle Problem Language Result Execution time Memory
408732 2021-05-19T14:58:34 Z Cyanmond Strange Device (APIO19_strange_device) C++17
100 / 100
 1936 ms 99552 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 18 ms 1356 KB Output is correct
3 Correct 18 ms 1452 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 19 ms 1432 KB Output is correct
17 Correct 177 ms 11832 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 420 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 1042 ms 21604 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1768 ms 80100 KB Output is correct
3 Correct 1822 ms 80068 KB Output is correct
4 Correct 1904 ms 80236 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1768 ms 80100 KB Output is correct
3 Correct 1822 ms 80068 KB Output is correct
4 Correct 1904 ms 80236 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1779 ms 80048 KB Output is correct
7 Correct 1808 ms 82260 KB Output is correct
8 Correct 1797 ms 82144 KB Output is correct
9 Correct 1877 ms 82168 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1768 ms 80100 KB Output is correct
3 Correct 1822 ms 80068 KB Output is correct
4 Correct 1904 ms 80236 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 170 ms 11844 KB Output is correct
7 Correct 170 ms 11836 KB Output is correct
8 Correct 172 ms 11816 KB Output is correct
9 Correct 174 ms 11832 KB Output is correct
10 Correct 172 ms 11844 KB Output is correct
11 Correct 174 ms 11836 KB Output is correct
12 Correct 175 ms 11824 KB Output is correct
13 Correct 175 ms 11736 KB Output is correct
14 Correct 169 ms 11844 KB Output is correct
15 Correct 180 ms 11832 KB Output is correct
16 Correct 182 ms 11820 KB Output is correct
17 Correct 175 ms 11816 KB Output is correct
18 Correct 1774 ms 80228 KB Output is correct
19 Correct 1846 ms 80092 KB Output is correct
20 Correct 1851 ms 80148 KB Output is correct
21 Correct 171 ms 11816 KB Output is correct
22 Correct 180 ms 11932 KB Output is correct
23 Correct 481 ms 18116 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 194 ms 11840 KB Output is correct
3 Correct 177 ms 11840 KB Output is correct
4 Correct 1837 ms 80068 KB Output is correct
5 Correct 180 ms 11816 KB Output is correct
6 Correct 184 ms 11816 KB Output is correct
7 Correct 181 ms 11820 KB Output is correct
8 Correct 182 ms 11860 KB Output is correct
9 Correct 179 ms 11844 KB Output is correct
10 Correct 174 ms 11816 KB Output is correct
11 Correct 175 ms 11820 KB Output is correct
12 Correct 182 ms 11948 KB Output is correct
13 Correct 183 ms 11824 KB Output is correct
14 Correct 1858 ms 80180 KB Output is correct
15 Correct 171 ms 11844 KB Output is correct
16 Correct 1771 ms 80172 KB Output is correct
17 Correct 1779 ms 80288 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 18 ms 1356 KB Output is correct
3 Correct 18 ms 1452 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 19 ms 1432 KB Output is correct
17 Correct 177 ms 11832 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 420 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 3 ms 332 KB Output is correct
27 Correct 3 ms 332 KB Output is correct
28 Correct 1042 ms 21604 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1768 ms 80100 KB Output is correct
31 Correct 1822 ms 80068 KB Output is correct
32 Correct 1904 ms 80236 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1779 ms 80048 KB Output is correct
35 Correct 1808 ms 82260 KB Output is correct
36 Correct 1797 ms 82144 KB Output is correct
37 Correct 1877 ms 82168 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 170 ms 11844 KB Output is correct
40 Correct 170 ms 11836 KB Output is correct
41 Correct 172 ms 11816 KB Output is correct
42 Correct 174 ms 11832 KB Output is correct
43 Correct 172 ms 11844 KB Output is correct
44 Correct 174 ms 11836 KB Output is correct
45 Correct 175 ms 11824 KB Output is correct
46 Correct 175 ms 11736 KB Output is correct
47 Correct 169 ms 11844 KB Output is correct
48 Correct 180 ms 11832 KB Output is correct
49 Correct 182 ms 11820 KB Output is correct
50 Correct 175 ms 11816 KB Output is correct
51 Correct 1774 ms 80228 KB Output is correct
52 Correct 1846 ms 80092 KB Output is correct
53 Correct 1851 ms 80148 KB Output is correct
54 Correct 171 ms 11816 KB Output is correct
55 Correct 180 ms 11932 KB Output is correct
56 Correct 481 ms 18116 KB Output is correct
57 Correct 1 ms 204 KB Output is correct
58 Correct 194 ms 11840 KB Output is correct
59 Correct 177 ms 11840 KB Output is correct
60 Correct 1837 ms 80068 KB Output is correct
61 Correct 180 ms 11816 KB Output is correct
62 Correct 184 ms 11816 KB Output is correct
63 Correct 181 ms 11820 KB Output is correct
64 Correct 182 ms 11860 KB Output is correct
65 Correct 179 ms 11844 KB Output is correct
66 Correct 174 ms 11816 KB Output is correct
67 Correct 175 ms 11820 KB Output is correct
68 Correct 182 ms 11948 KB Output is correct
69 Correct 183 ms 11824 KB Output is correct
70 Correct 1858 ms 80180 KB Output is correct
71 Correct 171 ms 11844 KB Output is correct
72 Correct 1771 ms 80172 KB Output is correct
73 Correct 1779 ms 80288 KB Output is correct
74 Correct 1 ms 204 KB Output is correct
75 Correct 1 ms 204 KB Output is correct
76 Correct 1 ms 204 KB Output is correct
77 Correct 1 ms 204 KB Output is correct
78 Correct 1 ms 204 KB Output is correct
79 Correct 17 ms 1448 KB Output is correct
80 Correct 1846 ms 99368 KB Output is correct
81 Correct 1865 ms 99412 KB Output is correct
82 Correct 1936 ms 99552 KB Output is correct
83 Correct 1889 ms 99464 KB Output is correct
84 Correct 1890 ms 99232 KB Output is correct
85 Correct 1824 ms 99532 KB Output is correct
86 Correct 476 ms 18144 KB Output is correct
87 Correct 1 ms 204 KB Output is correct