oj.uz

Submission #213010

# Submission time Handle Problem Language Result Execution time Memory
213010 2020-03-24T18:35:33 Z arman_ferdous Strange Device (APIO19_strange_device) C++17
10 / 100
 585 ms 16984 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 ll oo = 2e18;

vector<pair<ll,ll>> interval;

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

  int inf = 0, all = 0; ll sum = 0;
  ll g = __gcd(A, B + 1);
  ll K = A / g;
  ll T = K * B;

  if(K > oo / B) inf = 1;
  while(n--) {
    ll l, r;
    scanf("%lld %lld", &l, &r);

    if(r - l + 1 >= T) {
      all = 1;
      break;
    } 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 if(all) printf("%lld\n", T);
  else {
    ll ans = 0;
    sort(interval.begin(), interval.end());
    for(int i = 0; i < (int)interval.size(); i++) {
      ans += interval[i].second - interval[i].first + 1;
      if(i) ans -= max(interval[i - 1].second - interval[i].first + 1, 0ll);
    }
    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 5 ms 256 KB Output is correct
2 Incorrect 10 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 547 ms 16804 KB Output is correct
3 Correct 516 ms 16904 KB Output is correct
4 Correct 518 ms 16984 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 547 ms 16804 KB Output is correct
3 Correct 516 ms 16904 KB Output is correct
4 Correct 518 ms 16984 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 520 ms 16880 KB Output is correct
7 Correct 532 ms 16848 KB Output is correct
8 Correct 525 ms 16884 KB Output is correct
9 Correct 567 ms 16856 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 547 ms 16804 KB Output is correct
3 Correct 516 ms 16904 KB Output is correct
4 Correct 518 ms 16984 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 54 ms 2540 KB Output is correct
7 Correct 58 ms 2540 KB Output is correct
8 Correct 54 ms 2540 KB Output is correct
9 Correct 57 ms 2540 KB Output is correct
10 Correct 56 ms 2536 KB Output is correct
11 Correct 60 ms 2540 KB Output is correct
12 Correct 60 ms 2540 KB Output is correct
13 Correct 57 ms 2540 KB Output is correct
14 Correct 59 ms 2540 KB Output is correct
15 Incorrect 63 ms 2668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 61 ms 2524 KB Output is correct
3 Correct 63 ms 2540 KB Output is correct
4 Correct 585 ms 16848 KB Output is correct
5 Correct 58 ms 2540 KB Output is correct
6 Correct 57 ms 2548 KB Output is correct
7 Correct 58 ms 2548 KB Output is correct
8 Correct 60 ms 2540 KB Output is correct
9 Correct 62 ms 2540 KB Output is correct
10 Correct 58 ms 2540 KB Output is correct
11 Correct 65 ms 2540 KB Output is correct
12 Correct 59 ms 2540 KB Output is correct
13 Correct 58 ms 2540 KB Output is correct
14 Incorrect 579 ms 16852 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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