oj.uz

Submission #186837

# Submission time Handle Problem Language Result Execution time Memory
186837 2020-01-12T11:02:09 Z MiricaMatei Strange Device (APIO19_strange_device) C++14
10 / 100
 641 ms 69796 KB 
#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);
  }
  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: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 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 1400 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 372 KB Output is correct
5 Correct 450 ms 57840 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 577 ms 32464 KB Output is correct
3 Incorrect 579 ms 69792 KB Output isn't correct
4 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 Correct 577 ms 32464 KB Output is correct
3 Incorrect 579 ms 69792 KB Output isn't correct
4 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 Correct 577 ms 32464 KB Output is correct
3 Incorrect 579 ms 69792 KB Output isn't correct
4 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 Correct 63 ms 4096 KB Output is correct
3 Correct 61 ms 7784 KB Output is correct
4 Correct 641 ms 69664 KB Output is correct
5 Correct 61 ms 7784 KB Output is correct
6 Correct 62 ms 7808 KB Output is correct
7 Correct 62 ms 7840 KB Output is correct
8 Correct 63 ms 7840 KB Output is correct
9 Correct 61 ms 7824 KB Output is correct
10 Correct 61 ms 7760 KB Output is correct
11 Correct 63 ms 7800 KB Output is correct
12 Correct 56 ms 7768 KB Output is correct
13 Correct 62 ms 7744 KB Output is correct
14 Correct 623 ms 69796 KB Output is correct
15 Incorrect 64 ms 7828 KB Output isn't correct
16 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 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 1400 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -