oj.uz

Submission #186833

# Submission time Handle Problem Language Result Execution time Memory
186833 2020-01-12T10:53:12 Z MiricaMatei Strange Device (APIO19_strange_device) C++14
0 / 100
 595 ms 24728 KB 
#include <bits/stdc++.h>

using namespace std;

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

int 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);
  }
  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

strange_device.cpp: In function 'int main()':
strange_device.cpp:18:35: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
     scanf("%lld%lld", &l[i], &r[i]);
                       ~~~~~       ^
strange_device.cpp:18:35: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 7 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 595 ms 24728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 595 ms 24728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 595 ms 24728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 58 ms 3720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 7 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -