oj.uz

Submission #249111

# Submission time Handle Problem Language Result Execution time Memory
249111 2020-07-14T10:48:40 Z KoD Strange Device (APIO19_strange_device) C++17
15 / 100
 1873 ms 299276 KB 
#line 1 "main.cpp"

/**
 * @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 {
      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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 7 ms 1408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1039 ms 126572 KB Output is correct
3 Correct 1847 ms 299276 KB Output is correct
4 Correct 1873 ms 299216 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1039 ms 126572 KB Output is correct
3 Correct 1847 ms 299276 KB Output is correct
4 Correct 1873 ms 299216 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1532 ms 205176 KB Output is correct
7 Correct 853 ms 68844 KB Output is correct
8 Correct 1539 ms 205212 KB Output is correct
9 Correct 1648 ms 205164 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1039 ms 126572 KB Output is correct
3 Correct 1847 ms 299276 KB Output is correct
4 Correct 1873 ms 299216 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 129 ms 15028 KB Output is correct
7 Correct 153 ms 21816 KB Output is correct
8 Correct 140 ms 21704 KB Output is correct
9 Correct 154 ms 21816 KB Output is correct
10 Correct 109 ms 12480 KB Output is correct
11 Correct 143 ms 21684 KB Output is correct
12 Correct 150 ms 21792 KB Output is correct
13 Correct 147 ms 21804 KB Output is correct
14 Correct 68 ms 7644 KB Output is correct
15 Incorrect 135 ms 15396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 70 ms 6384 KB Output is correct
3 Correct 64 ms 6384 KB Output is correct
4 Correct 1090 ms 79980 KB Output is correct
5 Correct 83 ms 6256 KB Output is correct
6 Correct 76 ms 6256 KB Output is correct
7 Correct 73 ms 6256 KB Output is correct
8 Correct 97 ms 7112 KB Output is correct
9 Correct 103 ms 7372 KB Output is correct
10 Correct 71 ms 6256 KB Output is correct
11 Correct 72 ms 6256 KB Output is correct
12 Correct 62 ms 7648 KB Output is correct
13 Correct 78 ms 6836 KB Output is correct
14 Incorrect 669 ms 48812 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 7 ms 1408 KB Output isn't correct
3 Halted 0 ms 0 KB -