oj.uz

Submission #966635

# Submission time Handle Problem Language Result Execution time Memory
966635 2024-04-20T07:22:29 Z kilkuwu Strange Device (APIO19_strange_device) C++17
5 / 100
 379 ms 94524 KB 
#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];
  }

  if ((B + 1) % A == 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 = r;
      }
    }

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

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

  auto decompose = [&](int64_t t) -> std::pair<int64_t, int64_t> {
    return {t % B, t / B};
  };

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

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

    if (qr >= A) {
      segs.emplace_back(rl + ql * B, B - 1 + (A - 1) * B);
      auto num_shift = qr / A;
      qr -= num_shift * A;
      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 = r;
    }
  }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 4 ms 1496 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 349 ms 85472 KB Output is correct
3 Incorrect 349 ms 94392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 349 ms 85472 KB Output is correct
3 Incorrect 349 ms 94392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 349 ms 85472 KB Output is correct
3 Incorrect 349 ms 94392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 39 ms 10264 KB Output is correct
3 Correct 43 ms 10372 KB Output is correct
4 Correct 379 ms 94524 KB Output is correct
5 Correct 36 ms 10328 KB Output is correct
6 Correct 37 ms 10184 KB Output is correct
7 Correct 35 ms 10188 KB Output is correct
8 Correct 36 ms 10204 KB Output is correct
9 Correct 35 ms 10188 KB Output is correct
10 Correct 39 ms 10324 KB Output is correct
11 Correct 38 ms 10192 KB Output is correct
12 Correct 30 ms 10188 KB Output is correct
13 Correct 38 ms 10444 KB Output is correct
14 Incorrect 367 ms 93704 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 348 KB Output is correct
2 Incorrect 4 ms 1496 KB Output isn't correct
3 Halted 0 ms 0 KB -