oj.uz

Submission #781888

# Submission time Handle Problem Language Result Execution time Memory
781888 2023-07-13T12:42:42 Z kebine Strange Device (APIO19_strange_device) C++17
35 / 100
 347 ms 19576 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define keish                             ios_base::sync_with_stdio(0);       cin.tie(0); cout.tie(0)
      
using namespace std;

int n, a, b, l, r;

signed main(){
      keish;
      cin >> n >> a >> b;

      vector<pair<int, int>> v;
      int c = a / gcd(a, b + 1) * b;
      bool ok = 0;
      for(int i = 0; i < n; i++){
            cin >> l >> r;
            if(r - l + 1 >= c){
                  ok = 1;
            }

            l %= c, r %= c;

            if(l <= r){
                  v.push_back({l, r});
            }else{
                  v.push_back({l, c - 1});
                  v.push_back({0, r});
            }
      }

      if(ok){
            cout << c << '\n';
            return 0;
      }
      
      sort(v.begin(), v.end());

      int lf = v[0].fi, rg = v[0].se;
      int ans = 0;
      for(int i = 1; i < v.size(); i++){
            if(v[i].fi > rg){
                  ans += rg - lf + 1;
                  lf = v[i].fi, rg = v[i].se;
            }
            rg = max(rg, v[i].se);
      }
      ans += rg - lf + 1;

      cout << ans << '\n';
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:43:24: 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]
   43 |       for(int i = 1; i < v.size(); i++){
      |                      ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1060 KB Output is correct
3 Correct 4 ms 984 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 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 324 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 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 4 ms 984 KB Output is correct
17 Correct 39 ms 5748 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 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 218 ms 19416 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 317 ms 19576 KB Output is correct
3 Correct 316 ms 17312 KB Output is correct
4 Correct 310 ms 17420 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 317 ms 19576 KB Output is correct
3 Correct 316 ms 17312 KB Output is correct
4 Correct 310 ms 17420 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 325 ms 17272 KB Output is correct
7 Correct 310 ms 17332 KB Output is correct
8 Correct 303 ms 17300 KB Output is correct
9 Correct 339 ms 17460 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 317 ms 19576 KB Output is correct
3 Correct 316 ms 17312 KB Output is correct
4 Correct 310 ms 17420 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 33 ms 5312 KB Output is correct
7 Correct 34 ms 5632 KB Output is correct
8 Correct 30 ms 5572 KB Output is correct
9 Correct 31 ms 5500 KB Output is correct
10 Correct 37 ms 5556 KB Output is correct
11 Correct 34 ms 5496 KB Output is correct
12 Correct 38 ms 5560 KB Output is correct
13 Correct 33 ms 5464 KB Output is correct
14 Correct 31 ms 5512 KB Output is correct
15 Correct 36 ms 5556 KB Output is correct
16 Correct 36 ms 5504 KB Output is correct
17 Correct 35 ms 5700 KB Output is correct
18 Correct 312 ms 17324 KB Output is correct
19 Correct 314 ms 17360 KB Output is correct
20 Correct 333 ms 17316 KB Output is correct
21 Correct 34 ms 5472 KB Output is correct
22 Correct 32 ms 5528 KB Output is correct
23 Correct 100 ms 15176 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 36 ms 5648 KB Output is correct
3 Correct 36 ms 5240 KB Output is correct
4 Correct 347 ms 17300 KB Output is correct
5 Correct 33 ms 5572 KB Output is correct
6 Correct 35 ms 5560 KB Output is correct
7 Correct 33 ms 5592 KB Output is correct
8 Correct 37 ms 5528 KB Output is correct
9 Correct 33 ms 5532 KB Output is correct
10 Correct 41 ms 5808 KB Output is correct
11 Correct 41 ms 5504 KB Output is correct
12 Correct 29 ms 5572 KB Output is correct
13 Correct 33 ms 5560 KB Output is correct
14 Correct 331 ms 17244 KB Output is correct
15 Correct 37 ms 4720 KB Output is correct
16 Correct 302 ms 17388 KB Output is correct
17 Correct 317 ms 17376 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 4 ms 1060 KB Output is correct
3 Correct 4 ms 984 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 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 324 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 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 4 ms 984 KB Output is correct
17 Correct 39 ms 5748 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -