oj.uz

Submission #224438

# Submission time Handle Problem Language Result Execution time Memory
224438 2020-04-17T22:36:15 Z Bruteforceman Strange Device (APIO19_strange_device) C++11
15 / 100
 2190 ms 53628 KB 
#include <bits/stdc++.h>
using namespace std;
const long long INF = 3e18;

int main() {
  int n;
  long long A, B;
  cin >> n >> A >> B;
  long long per = A / __gcd(A, B + 1);
  if((INF / B) < per) per = INF;
  else per = per * B;
  vector <pair <long long, long long>> v;
  auto addRange = [&] (long long p, long long q) {
    v.emplace_back(q, p);
  };
  for(int i = 0; i < n; i++) {
    long long p, q;
    cin >> p >> q;
    if((q - p + 1) >= per) {
      cout << per << endl;
      exit(0);
    } 
    p %= per; q %= per;
    if(p <= q) {
      addRange(p, q);
    } else {
      addRange(p, per - 1);
      addRange(0, q);
    }
  }
  sort(v.begin(), v.end());
  long long ans = 0;
  long long last = -1;
  for(auto i : v) {
    long long l = i.second;
    long long r = i.first;
    ans += r - max(last + 1, l) + 1;
    last = r;
  }
  cout << ans << endl;
  return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 7 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 4 ms 384 KB Output is correct
2 Correct 2111 ms 16976 KB Output is correct
3 Correct 2126 ms 17164 KB Output is correct
4 Correct 2137 ms 53584 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 2111 ms 16976 KB Output is correct
3 Correct 2126 ms 17164 KB Output is correct
4 Correct 2137 ms 53584 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 2148 ms 53328 KB Output is correct
7 Correct 2130 ms 53536 KB Output is correct
8 Correct 2166 ms 53628 KB Output is correct
9 Correct 2131 ms 53304 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 2111 ms 16976 KB Output is correct
3 Correct 2126 ms 17164 KB Output is correct
4 Correct 2137 ms 53584 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 218 ms 5848 KB Output is correct
7 Correct 216 ms 5860 KB Output is correct
8 Correct 216 ms 5732 KB Output is correct
9 Correct 220 ms 5860 KB Output is correct
10 Correct 213 ms 5732 KB Output is correct
11 Correct 219 ms 5836 KB Output is correct
12 Correct 213 ms 5860 KB Output is correct
13 Correct 221 ms 5736 KB Output is correct
14 Correct 218 ms 5860 KB Output is correct
15 Incorrect 218 ms 5732 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 220 ms 3688 KB Output is correct
3 Correct 217 ms 3560 KB Output is correct
4 Correct 2190 ms 17152 KB Output is correct
5 Correct 221 ms 3560 KB Output is correct
6 Correct 218 ms 3520 KB Output is correct
7 Correct 218 ms 3564 KB Output is correct
8 Correct 218 ms 3564 KB Output is correct
9 Correct 215 ms 3564 KB Output is correct
10 Correct 217 ms 3560 KB Output is correct
11 Correct 217 ms 3564 KB Output is correct
12 Correct 211 ms 3560 KB Output is correct
13 Correct 215 ms 3560 KB Output is correct
14 Incorrect 2160 ms 17008 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 384 KB Output is correct
2 Incorrect 27 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -