Submission #1020184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020184		avighna	Strange Device (APIO19_strange_device)	C++17	100 / 100	562 ms	97676 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;

  // w (B + 1) mod A = 0
  ll cycle = (b / std::gcd(a, b + 1) >= (ll(1e18) + 1) / a)
                 ? ll(1e18) + 1
                 : 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;
    if (r - l + 1 >= cycle) {
      std::cout << cycle << "\n";
      return 0;
    }
    ll _l = l % cycle, _r = r % cycle;
    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;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30