oj.uz

Submission #723177

# Submission time Handle Problem Language Result Execution time Memory
723177 2023-04-13T10:00:48 Z culver0412 Strange Device (APIO19_strange_device) C++17
35 / 100
 1329 ms 28820 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
    long long int n,a,b;
    cin >> n >> a >> b;
    long long int x=a/gcd(a,b+1)*b;
    vector<pair<long long int,long long int>> ranges;
    for(int i=0;i<n;i++){
        long long int l,r;
        cin >> l >> r;
        if(r-l+1>=x){
            cout << x << endl;
            return 0;
        }
        l%=x;
        r%=x;
        if(l<=r){
            ranges.push_back({l,r});
        }
        else{
            ranges.push_back({0,r});
            ranges.push_back({l,x-1});
        }
    }
    sort(ranges.begin(),ranges.end());
    long long int curl=ranges[0].first,curr=ranges[0].second,ans=0;
    for(int i=1;i<ranges.size();i++){
        pair<long long int,long long int> range=ranges[i];
        if(curr<range.first){
            ans+=(curr-curl+1);
            curl=range.first;
            curr=range.second;
        }
        else{
            curr=max(curr,range.second);
        }
    }
    ans+=(curr-curl+1);
    cout << ans << endl;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 16 ms 852 KB Output is correct
3 Correct 14 ms 820 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 129 ms 5688 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 1 ms 212 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 2 ms 312 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 900 ms 16832 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 1251 ms 16924 KB Output is correct
3 Correct 1241 ms 16860 KB Output is correct
4 Correct 1278 ms 27940 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 1251 ms 16924 KB Output is correct
3 Correct 1241 ms 16860 KB Output is correct
4 Correct 1278 ms 27940 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1263 ms 28068 KB Output is correct
7 Correct 1263 ms 28036 KB Output is correct
8 Correct 1282 ms 28172 KB Output is correct
9 Correct 1296 ms 28100 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 1251 ms 16924 KB Output is correct
3 Correct 1241 ms 16860 KB Output is correct
4 Correct 1278 ms 27940 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 133 ms 5664 KB Output is correct
7 Correct 127 ms 5688 KB Output is correct
8 Correct 129 ms 5824 KB Output is correct
9 Correct 132 ms 5652 KB Output is correct
10 Correct 128 ms 5696 KB Output is correct
11 Correct 128 ms 5600 KB Output is correct
12 Correct 128 ms 5600 KB Output is correct
13 Correct 131 ms 5568 KB Output is correct
14 Correct 141 ms 5708 KB Output is correct
15 Correct 129 ms 5672 KB Output is correct
16 Correct 129 ms 5724 KB Output is correct
17 Correct 130 ms 5668 KB Output is correct
18 Correct 1287 ms 28556 KB Output is correct
19 Correct 1257 ms 27896 KB Output is correct
20 Correct 1329 ms 27872 KB Output is correct
21 Correct 133 ms 5660 KB Output is correct
22 Correct 126 ms 5688 KB Output is correct
23 Correct 424 ms 18412 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 144 ms 2624 KB Output is correct
3 Correct 130 ms 2676 KB Output is correct
4 Correct 1314 ms 16776 KB Output is correct
5 Correct 131 ms 2620 KB Output is correct
6 Correct 138 ms 2612 KB Output is correct
7 Correct 130 ms 2624 KB Output is correct
8 Correct 129 ms 2800 KB Output is correct
9 Correct 126 ms 2636 KB Output is correct
10 Correct 130 ms 2672 KB Output is correct
11 Correct 128 ms 2632 KB Output is correct
12 Correct 122 ms 2568 KB Output is correct
13 Correct 128 ms 2796 KB Output is correct
14 Correct 1282 ms 16860 KB Output is correct
15 Correct 134 ms 2656 KB Output is correct
16 Correct 1275 ms 28820 KB Output is correct
17 Correct 1253 ms 28620 KB Output is correct
18 Incorrect 1 ms 300 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 16 ms 852 KB Output is correct
3 Correct 14 ms 820 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 129 ms 5688 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -