oj.uz

Submission #784507

# Submission time Handle Problem Language Result Execution time Memory
784507 2023-07-16T07:36:35 Z andecaandeci Strange Device (APIO19_strange_device) C++17
5 / 100
 1488 ms 63672 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*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;
  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:54: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]
   54 |   for (int i = 0; i < sg.size(); i++) {
      |                   ~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 972 KB Output is correct
3 Correct 14 ms 924 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 0 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 1 ms 340 KB Output is correct
5 Correct 765 ms 33160 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 1295 ms 63608 KB Output is correct
3 Incorrect 1129 ms 63608 KB Output isn't correct
4 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 1295 ms 63608 KB Output is correct
3 Incorrect 1129 ms 63608 KB Output isn't correct
4 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 1295 ms 63608 KB Output is correct
3 Incorrect 1129 ms 63608 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 124 ms 6920 KB Output is correct
3 Correct 121 ms 6952 KB Output is correct
4 Correct 1488 ms 63672 KB Output is correct
5 Correct 123 ms 7028 KB Output is correct
6 Correct 123 ms 7052 KB Output is correct
7 Correct 125 ms 7032 KB Output is correct
8 Correct 124 ms 6936 KB Output is correct
9 Correct 119 ms 6932 KB Output is correct
10 Correct 127 ms 7004 KB Output is correct
11 Correct 121 ms 6928 KB Output is correct
12 Correct 115 ms 7004 KB Output is correct
13 Correct 123 ms 7000 KB Output is correct
14 Correct 1276 ms 63600 KB Output is correct
15 Incorrect 130 ms 7076 KB Output isn't correct
16 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 14 ms 972 KB Output is correct
3 Correct 14 ms 924 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -