Submission #1019351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019351		avighna	Strange Device (APIO19_strange_device)	C++17	0 / 100	5046 ms	524288 KiB

strange_device

#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::map<ll, ll> mp;
    while (n--) {
      ll l, r;
      std::cin >> l >> r;
      if (l != r && l % cycle == r % cycle) {
        l %= cycle, r = cycle - 1;
      } else {
        l %= cycle, r %= cycle;
      }
      mp[l] = std::max(mp[l], r);
    }
    ll right = 0;
    ll ans = 0;
    for (auto &i : mp) {
      if (i.second < right) {
        continue;
      }
      ans += i.second - right + 1;
      right = i.second;
    }
    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: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30