oj.uz

Submission #213041

# Submission time Handle Problem Language Result Execution time Memory
213041 2020-03-24T19:31:40 Z arman_ferdous Strange Device (APIO19_strange_device) C++17
35 / 100
 576 ms 21636 KB 
/* at time = 0, (x, y) = (0, 0)
 * we need to find minimum t > 0, such that (x, y) = 0 again ie. the cycle period.
 * now, y = 0 = t % B => t = K * B (for some integer K)
 * putting t in x's eqn and simplifying gives us a nice formula
 * K * (B + 1) % A = 0
 * from here it is easy to find K's value. 
 * answering queries are just merging intervals
 */

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

using ll = long long;
const double oo = 1e19;

vector<pair<ll,ll>> interval;

int main () {
  int n;
  ll A, B;
  scanf("%d %lld %lld", &n, &A, &B);

  int inf = 0; ll sum = 0;
  ll g = __gcd(A, B + 1);
  ll K = A / g;
  ll T = K * B;
  
  if(K * 1.0 > oo / B * 1.0) inf = 1;
  while(n--) {
    ll l, r;
    scanf("%lld %lld", &l, &r);

    if(r - l + 1 >= T) {
      printf("%lld\n", T);
      return 0;
    } sum += r - l + 1;

    ll le = l % T;
    ll ri = r % T;
    if(le <= ri) {
      interval.push_back({le, ri});

    }
    else {
      interval.push_back({0, ri});
      interval.push_back({le, T - 1});
    }
  }

  if(inf) printf("%lld\n", sum);
  else {
    ll ans = 0, ptr = -1;
    sort(interval.begin(), interval.end());
    for(int i = 0; i < (int)interval.size(); i++) {
      if(ptr < interval[i].first) {
        ans += interval[i].second - interval[i].first + 1;
        ptr = interval[i].second;
      }
      else {
        ans += max(0ll, interval[i].second - ptr);
        ptr = max(ptr, interval[i].second);
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 10 ms 1152 KB Output is correct
17 Correct 63 ms 5732 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Incorrect 4 ms 256 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 419 ms 19664 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 530 ms 17676 KB Output is correct
3 Correct 523 ms 17744 KB Output is correct
4 Correct 497 ms 17616 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 530 ms 17676 KB Output is correct
3 Correct 523 ms 17744 KB Output is correct
4 Correct 497 ms 17616 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 510 ms 17488 KB Output is correct
7 Correct 533 ms 17488 KB Output is correct
8 Correct 511 ms 17488 KB Output is correct
9 Correct 560 ms 17696 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 530 ms 17676 KB Output is correct
3 Correct 523 ms 17744 KB Output is correct
4 Correct 497 ms 17616 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 57 ms 3180 KB Output is correct
7 Correct 67 ms 3180 KB Output is correct
8 Correct 56 ms 3196 KB Output is correct
9 Correct 55 ms 3180 KB Output is correct
10 Correct 57 ms 3180 KB Output is correct
11 Correct 59 ms 3176 KB Output is correct
12 Correct 54 ms 3180 KB Output is correct
13 Correct 58 ms 3188 KB Output is correct
14 Correct 57 ms 3180 KB Output is correct
15 Correct 60 ms 3180 KB Output is correct
16 Correct 60 ms 5736 KB Output is correct
17 Correct 57 ms 5736 KB Output is correct
18 Correct 553 ms 21636 KB Output is correct
19 Correct 520 ms 21452 KB Output is correct
20 Correct 573 ms 21460 KB Output is correct
21 Correct 59 ms 5740 KB Output is correct
22 Correct 52 ms 5736 KB Output is correct
23 Correct 204 ms 18516 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 61 ms 3180 KB Output is correct
3 Correct 60 ms 3180 KB Output is correct
4 Correct 576 ms 17620 KB Output is correct
5 Correct 57 ms 3180 KB Output is correct
6 Correct 59 ms 3180 KB Output is correct
7 Correct 64 ms 3180 KB Output is correct
8 Correct 58 ms 3184 KB Output is correct
9 Correct 64 ms 3180 KB Output is correct
10 Correct 58 ms 3180 KB Output is correct
11 Correct 59 ms 3180 KB Output is correct
12 Correct 51 ms 3180 KB Output is correct
13 Correct 60 ms 3176 KB Output is correct
14 Correct 567 ms 17488 KB Output is correct
15 Correct 68 ms 5988 KB Output is correct
16 Correct 530 ms 21456 KB Output is correct
17 Correct 530 ms 21584 KB Output is correct
18 Incorrect 5 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 10 ms 1152 KB Output is correct
17 Correct 63 ms 5732 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct