Submission #186848

#	Time	Username	Problem	Language	Result	Execution time	Memory
186848		MiricaMatei	Strange Device (APIO19_strange_device)	C++14	100 / 100	646 ms	69992 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
const long long INF = 1000000000000000000LL;

long long l[MAXN], r[MAXN];

int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  long long n, a, b;
  scanf("%lld%lld%lld", &n, &a, &b);
  long long s = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%lld%lld", &l[i], &r[i]);
    s += (r[i] - l[i] + 1);
  }
  a /= __gcd(a, b + 1);
  if (a >= INF / b) {
    printf("%lld\n", s);
    return 0;
  }
  long long P = a * b;
  vector<pair<long long, long long> >interval;
  for (int i = 1; i <= n; ++i) {
    long long lg = r[i] - l[i] + 1;
    if (lg >= P) {
      printf("%lld\n", P);
      return 0;
    }
    if (r[i] % P >= l[i] % P) {
      interval.push_back({l[i] % P, r[i] % P});
    } else {
      interval.push_back({0, r[i] % P});
      interval.push_back({l[i] % P, P - 1});
    }
  }
  sort(interval.begin(), interval.end());
  long long mx = 0;
  long long ans = 0, lg = 0;
  for (auto it:interval) {
    //fprintf(stderr, "%lld %lld\n", it.first, it.second);
    lg += (it.second - it.first + 1);
    ans += max(0LL, it.second - max(it.first, mx) + 1);
    mx = max(mx, it.second + 1);
  }
  assert(lg == s);
  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &n, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld", &l[i], &r[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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