oj.uz

Submission #784502

# Submission time Handle Problem Language Result Execution time Memory
784502 2023-07-16T07:33:05 Z makanhulia Strange Device (APIO19_strange_device) C++17
5 / 100
 1407 ms 33356 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);
// }

bool comp(pair<int, int> a, pair<int, int> b) {
  return (a.first < b.first or (a.first == b.first and a.second < b.second));
}

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(), comp);

  int cnt = 0, l2, ans = 0;
  // 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});
      ans += sg[i].first-l2+1.;
    }
  }
  cout << ans << endl;

  // 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:53: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]
   53 |   for (int i = 0; i < sg.size(); i++) {
      |                   ~~^~~~~~~~~~~
strange_device.cpp:62:25: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |       ans += sg[i].first-l2+1.;

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 12 ms 848 KB Output is correct
3 Correct 13 ms 836 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 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 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 12 ms 848 KB Output is correct
17 Correct 133 ms 4908 KB Output is correct
18 Incorrect 0 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 796 ms 33296 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1228 ms 33204 KB Output is correct
3 Correct 1269 ms 33168 KB Output is correct
4 Incorrect 1219 ms 33172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1228 ms 33204 KB Output is correct
3 Correct 1269 ms 33168 KB Output is correct
4 Incorrect 1219 ms 33172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1228 ms 33204 KB Output is correct
3 Correct 1269 ms 33168 KB Output is correct
4 Incorrect 1219 ms 33172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 128 ms 4912 KB Output is correct
3 Correct 123 ms 4668 KB Output is correct
4 Correct 1407 ms 33356 KB Output is correct
5 Correct 129 ms 4748 KB Output is correct
6 Correct 151 ms 4716 KB Output is correct
7 Correct 126 ms 4784 KB Output is correct
8 Correct 130 ms 4712 KB Output is correct
9 Correct 127 ms 4776 KB Output is correct
10 Correct 128 ms 4772 KB Output is correct
11 Correct 123 ms 4720 KB Output is correct
12 Incorrect 116 ms 4668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 12 ms 848 KB Output is correct
3 Correct 13 ms 836 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 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 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 12 ms 848 KB Output is correct
17 Correct 133 ms 4908 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -