Submission #224438

#	Time	Username	Problem	Language	Result	Execution time	Memory
224438		Bruteforceman	Strange Device (APIO19_strange_device)	C++11	15 / 100	2190 ms	53628 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
const long long INF = 3e18;

int main() {
  int n;
  long long A, B;
  cin >> n >> A >> B;
  long long per = A / __gcd(A, B + 1);
  if((INF / B) < per) per = INF;
  else per = per * B;
  vector <pair <long long, long long>> v;
  auto addRange = [&] (long long p, long long q) {
    v.emplace_back(q, p);
  };
  for(int i = 0; i < n; i++) {
    long long p, q;
    cin >> p >> q;
    if((q - p + 1) >= per) {
      cout << per << endl;
      exit(0);
    } 
    p %= per; q %= per;
    if(p <= q) {
      addRange(p, q);
    } else {
      addRange(p, per - 1);
      addRange(0, q);
    }
  }
  sort(v.begin(), v.end());
  long long ans = 0;
  long long last = -1;
  for(auto i : v) {
    long long l = i.second;
    long long r = i.first;
    ans += r - max(last + 1, l) + 1;
    last = r;
  }
  cout << ans << endl;
  return 0;
}

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