oj.uz

Submission #1020072

# Submission time Handle Problem Language Result Execution time Memory
1020072 2024-07-11T13:32:15 Z avighna Strange Device (APIO19_strange_device) C++17
15 / 100
 5000 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 (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;
    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 << st.size() << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 29 ms 12704 KB Output is correct
3 Correct 44 ms 18260 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 6 ms 1372 KB Output is correct
10 Correct 0 ms 348 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 24 ms 7004 KB Output is correct
16 Correct 19 ms 7112 KB Output is correct
17 Correct 39 ms 10320 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1802 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 86 ms 32268 KB Output is correct
3 Correct 107 ms 32224 KB Output is correct
4 Correct 73 ms 30548 KB Output is correct
5 Execution timed out 5010 ms 62544 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 465 ms 115824 KB Output is correct
3 Correct 547 ms 115896 KB Output is correct
4 Correct 511 ms 116128 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 465 ms 115824 KB Output is correct
3 Correct 547 ms 115896 KB Output is correct
4 Correct 511 ms 116128 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 1722 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 348 KB Output is correct
2 Correct 465 ms 115824 KB Output is correct
3 Correct 547 ms 115896 KB Output is correct
4 Correct 511 ms 116128 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 160 ms 66516 KB Output is correct
7 Runtime error 1463 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 348 KB Output is correct
2 Runtime error 948 ms 524288 KB Execution killed with signal 9
3 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 Correct 29 ms 12704 KB Output is correct
3 Correct 44 ms 18260 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 6 ms 1372 KB Output is correct
10 Correct 0 ms 348 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 24 ms 7004 KB Output is correct
16 Correct 19 ms 7112 KB Output is correct
17 Correct 39 ms 10320 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Runtime error 1802 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -