Submission #749218

#	Time	Username	Problem	Language	Result	Execution time	Memory
749218		NeroZein	Strange Device (APIO19_strange_device)	C++17	100 / 100	547 ms	68880 KiB

strange_device

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; 
  long long a, b;
  cin >> n >> a >> b;
  a /= gcd(a, b + 1); 
  long long period = 1e18 + 1; 
  if (a <= LLONG_MAX / b) {
    period = a * b; 
  }
  vector<long long> l(n), r(n); 
  vector<pair<long long,long long>> v; 
  for (int i = 0; i < n; ++i) {
    cin >> l[i] >> r[i]; 
    if (r[i] - l[i] + 1 >= period) {
      cout << period << '\n';
      return 0; 
    }
    l[i] %= period;
    r[i] %= period; 
    if (l[i] <= r[i]) {
      v.emplace_back(l[i], r[i]); 
    } else {
      v.emplace_back(l[i], period - 1);
      v.emplace_back(0, r[i]); 
    }
  }
  sort(v.begin(), v.end()); 
  long long cl = 0; 
  long long cr = -1;
  long long ans = 0;  
  for (int i = 0; i < (int) v.size(); ++i) {
    auto [x, y] = v[i];
    if (x > cr) {
      ans += cr - cl + 1; 
      cl = x; cr = y; 
    } else {
      cr = max(cr, y); 
    }
  }
  ans += cr - cl + 1; 
  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