oj.uz

Submission #781898

# Submission time Handle Problem Language Result Execution time Memory
781898 2023-07-13T12:51:44 Z devariaota Strange Device (APIO19_strange_device) C++17
35 / 100
 357 ms 18280 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);
      c *= 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:44: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]
   44 |       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 984 KB Output is correct
3 Correct 4 ms 976 KB Output is correct
4 Correct 1 ms 212 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 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 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 1048 KB Output is correct
17 Correct 36 ms 3832 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 0 ms 320 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 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 213 ms 18120 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 311 ms 18280 KB Output is correct
3 Correct 309 ms 17404 KB Output is correct
4 Correct 320 ms 17328 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 311 ms 18280 KB Output is correct
3 Correct 309 ms 17404 KB Output is correct
4 Correct 320 ms 17328 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 311 ms 17348 KB Output is correct
7 Correct 314 ms 17372 KB Output is correct
8 Correct 307 ms 17348 KB Output is correct
9 Correct 348 ms 17576 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 311 ms 18280 KB Output is correct
3 Correct 309 ms 17404 KB Output is correct
4 Correct 320 ms 17328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 39 ms 3732 KB Output is correct
7 Correct 37 ms 3880 KB Output is correct
8 Correct 36 ms 3704 KB Output is correct
9 Correct 33 ms 3716 KB Output is correct
10 Correct 31 ms 3724 KB Output is correct
11 Correct 33 ms 3772 KB Output is correct
12 Correct 39 ms 3768 KB Output is correct
13 Correct 34 ms 3772 KB Output is correct
14 Correct 31 ms 3728 KB Output is correct
15 Correct 36 ms 3772 KB Output is correct
16 Correct 34 ms 3784 KB Output is correct
17 Correct 35 ms 3728 KB Output is correct
18 Correct 311 ms 17408 KB Output is correct
19 Correct 298 ms 17416 KB Output is correct
20 Correct 351 ms 17424 KB Output is correct
21 Correct 35 ms 3696 KB Output is correct
22 Correct 31 ms 3800 KB Output is correct
23 Correct 101 ms 11056 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 35 ms 3524 KB Output is correct
3 Correct 35 ms 3424 KB Output is correct
4 Correct 357 ms 17364 KB Output is correct
5 Correct 35 ms 3724 KB Output is correct
6 Correct 37 ms 3436 KB Output is correct
7 Correct 36 ms 3784 KB Output is correct
8 Correct 36 ms 3452 KB Output is correct
9 Correct 36 ms 3564 KB Output is correct
10 Correct 34 ms 3596 KB Output is correct
11 Correct 34 ms 3540 KB Output is correct
12 Correct 32 ms 3592 KB Output is correct
13 Correct 34 ms 3856 KB Output is correct
14 Correct 352 ms 17280 KB Output is correct
15 Correct 39 ms 3476 KB Output is correct
16 Correct 303 ms 17400 KB Output is correct
17 Correct 301 ms 17360 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 984 KB Output is correct
3 Correct 4 ms 976 KB Output is correct
4 Correct 1 ms 212 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 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 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 1048 KB Output is correct
17 Correct 36 ms 3832 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -