oj.uz

Submission #784487

# Submission time Handle Problem Language Result Execution time Memory
784487 2023-07-16T07:24:31 Z devariaota Strange Device (APIO19_strange_device) C++17
35 / 100
 1292 ms 64732 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
// #define i128 long long
#define i128 __int128_t

int n, a, b;
vector<pair<int, int>> sg;
const int maks = 1e18;

// i128 gcd(i128 a, i128 b) {
//   if (b == 0) return a;
//   return gcd(b, a%b);
// }

signed main() {
  i128 temp;
  // int temp;
  int size;
  cin >> n >> a >> b;
  temp = (a/__gcd(a,b+1))*b;
  // if ((b+1 % a) == 0) size = b;
  // if (temp > maks) size = maks;
  // else size = temp;
  size = temp;

  int l, r;
  for (int i = 0; i < n; i++) {
    cin >> l >> r;
    // cout << l << " " << r << endl;
    if (r - l + 1 >= size) {
      cout << size << endl;
      return 0;
    } else if (l%size > r%size) {
      sg.push_back({l%size, 1});
      sg.push_back({size-1, 2});
      sg.push_back({0, 1});
      sg.push_back({r%size, 2});
    } else {
      sg.push_back({l%size, 1});
      sg.push_back({r%size, 2});
    }
  }
  sort(sg.begin(), sg.end());

  int cnt = 0, l2;
  vector<pair<int, int>> ans;
  for (int i = 0; i < sg.size(); i++) {
    // cout << sg[i].first << " " << sg[i].second << endl;
    if (sg[i].second == 1) {
      if (cnt == 0) l2 = sg[i].first;
      cnt++;
    } else cnt--;

    if (cnt == 0) ans.push_back({l2, sg[i].first});
  }

  int res = 0;
  for (auto i: ans) {
    // cout << i.first << " " << i.second << endl;
    res += (i.second - i.first + 1);
  }
  cout << res << endl;

}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:49:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < sg.size(); i++) {
      |                   ~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 12 ms 1412 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 12 ms 1292 KB Output is correct
17 Correct 132 ms 8348 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 777 ms 33904 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1147 ms 64496 KB Output is correct
3 Correct 1148 ms 64732 KB Output is correct
4 Correct 1134 ms 63652 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1147 ms 64496 KB Output is correct
3 Correct 1148 ms 64732 KB Output is correct
4 Correct 1134 ms 63652 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1149 ms 63712 KB Output is correct
7 Correct 1108 ms 63736 KB Output is correct
8 Correct 1093 ms 63652 KB Output is correct
9 Correct 1154 ms 63600 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1147 ms 64496 KB Output is correct
3 Correct 1148 ms 64732 KB Output is correct
4 Correct 1134 ms 63652 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 107 ms 7596 KB Output is correct
7 Correct 107 ms 7648 KB Output is correct
8 Correct 107 ms 7600 KB Output is correct
9 Correct 107 ms 7648 KB Output is correct
10 Correct 112 ms 7612 KB Output is correct
11 Correct 107 ms 7592 KB Output is correct
12 Correct 105 ms 7736 KB Output is correct
13 Correct 110 ms 7612 KB Output is correct
14 Correct 127 ms 7664 KB Output is correct
15 Correct 112 ms 7648 KB Output is correct
16 Correct 110 ms 7644 KB Output is correct
17 Correct 105 ms 7632 KB Output is correct
18 Correct 1106 ms 63596 KB Output is correct
19 Correct 1061 ms 63736 KB Output is correct
20 Correct 1230 ms 63796 KB Output is correct
21 Correct 115 ms 7332 KB Output is correct
22 Correct 104 ms 7316 KB Output is correct
23 Correct 337 ms 17032 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 113 ms 7664 KB Output is correct
3 Correct 124 ms 7344 KB Output is correct
4 Correct 1292 ms 64260 KB Output is correct
5 Correct 110 ms 7340 KB Output is correct
6 Correct 111 ms 7392 KB Output is correct
7 Correct 112 ms 7368 KB Output is correct
8 Correct 120 ms 7512 KB Output is correct
9 Correct 112 ms 7472 KB Output is correct
10 Correct 112 ms 7364 KB Output is correct
11 Correct 111 ms 7360 KB Output is correct
12 Correct 107 ms 7420 KB Output is correct
13 Correct 112 ms 7372 KB Output is correct
14 Correct 1157 ms 64228 KB Output is correct
15 Correct 115 ms 7176 KB Output is correct
16 Correct 1075 ms 63656 KB Output is correct
17 Correct 1153 ms 63608 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 12 ms 1412 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 12 ms 1292 KB Output is correct
17 Correct 132 ms 8348 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -