Submission #1172454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172454		fryingduc	Strange Device (APIO19_strange_device)	C++20	100 / 100	585 ms	63132 KiB

strange_device

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 6;
const long long inf = 1e18;
int n;
long long a, b;

void solve() {
  cin >> n >> a >> b;
  long long d = __gcd(b + 1, a);
  if (inf / b < a / d) {
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
      long long l, r; cin >> l >> r;
      res += (r - l + 1);
    }
    cout << res;
    return;
  }
  long long g = (a / d) * b;
//  debug(g);
  map<long long, int> mp;
  for (int i = 1; i <= n; ++i) {
    long long l, r; cin >> l >> r;
    if (r - l >= g) {
      cout << g << '\n';
      return;
    }
    l %= g, r %= g;
    ++mp[l], --mp[r + 1];
    if (l > r) {
      ++mp[0];
      --mp[g];
    }
  }
  long long res = 0;
  long long prv = 0;
  long long cur = 0;
  for (auto [x, y] : mp) {
    if (cur == 0) {
      res += x - prv;
    }
    cur += y;
    if (cur == 0) {
      prv = x;
    }
  }
  res += (g - prv);
  cout << g - res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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