oj.uz

답안 #966635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966635 2024-04-20T07:22:29 Z kilkuwu 이상한 기계 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -