Submission #224436

#	Time	Username	Problem	Language	Result	Execution time	Memory
224436		Bruteforceman	Strange Device (APIO19_strange_device)	C++11	5 / 100	2261 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;
  for(int t = 0; t < 100; t++) {
//    cout << t << " "  << (t + (t / B)) % A << " " << t % B << endl;
  }
  long long per;
  if((INF / A) < B) {
    per = INF;
  } else {
    per = A * B;
  }
  vector <pair <long long, long long>> v;
  auto addRange = [&] (long long p, long long q) {
    v.emplace_back(q, p);
 //   cout << p << " " << q << endl;
  };
  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;
//    cout << "from " << last << " to " << min << endl;
    last = r;
  }
  cout << ans << endl;
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 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