oj.uz

Submission #1020145

# Submission time Handle Problem Language Result Execution time Memory
1020145 2024-07-11T15:45:45 Z avighna Strange Device (APIO19_strange_device) C++17
10 / 100
 1743 ms 524288 KB 
#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, a, b;
  std::cin >> n >> a >> b;

  if (a < b || b == 1) {
    // (2x % a, 0)
    // 2x % a == 0
    // if a is odd, then the cycle is of length a (the 2 will never contribute)
    // if a is even, then the cycle of of length a/2
    ll cycle = a % 2 == 0 ? a / 2 : a;
    if (a < b) {
      cycle = a / std::gcd(a, b + 1) * b;
    }
    std::vector<std::pair<ll, ll>> ranges;
    std::map<ll, ll> mp;
    while (n--) {
      ll l, r;
      std::cin >> l >> r;
      ll _l = l % cycle, _r = r % cycle;
      if (r - l + 1 >= cycle) {
        std::cout << cycle << "\n";
        return 0;
      }
      if (_l > _r) {
        ranges.push_back({_l, cycle - 1});
        ranges.push_back({0, _r});
      } else {
        ranges.push_back({_l, _r});
      }
    }
    for (auto &[l, r] : ranges) {
      mp[l] = std::max(mp[l], r);
    }
    ll right = 0;
    ll ans = 0;
    for (auto &i : mp) {
      if (i.second < right) {
        continue;
      }
      right = std::max(right, i.first);
      ans += i.second - right + 1;
      right = i.second + 1;
    }
    std::cout << ans << "\n";
    return 0;
  }

  std::set<std::pair<ll, ll>> st;
  while (n--) {
    ll l, r;
    std::cin >> l >> r;
    for (ll x = l; x <= r; ++x) {
      st.insert({(x + x / b) % a, x % b});
      //   std::cout << "(" << (x + x / b) % a << " " << x % b << "), ";
      //   std::cout << st.size() << "\n";
    }
  }
  std::cout << st.size() << "\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 1500 KB Output is correct
3 Correct 4 ms 1428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 19 ms 7120 KB Output is correct
17 Correct 48 ms 11204 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 88 ms 32272 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 78 ms 30540 KB Output is correct
5 Correct 188 ms 35452 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 483 ms 106696 KB Output is correct
3 Correct 509 ms 106780 KB Output is correct
4 Correct 522 ms 106764 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 483 ms 106696 KB Output is correct
3 Correct 509 ms 106780 KB Output is correct
4 Correct 522 ms 106764 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1743 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 483 ms 106696 KB Output is correct
3 Correct 509 ms 106780 KB Output is correct
4 Correct 522 ms 106764 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 150 ms 65844 KB Output is correct
7 Runtime error 1396 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 47 ms 11304 KB Output is correct
3 Correct 49 ms 11208 KB Output is correct
4 Runtime error 1626 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 1500 KB Output is correct
3 Correct 4 ms 1428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 19 ms 7120 KB Output is correct
17 Correct 48 ms 11204 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -