oj.uz

Submission #703046

# Submission time Handle Problem Language Result Execution time Memory
703046 2023-02-25T18:54:23 Z Elvin_Fritl Strange Device (APIO19_strange_device) C++17
65 / 100
 1502 ms 39736 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define big 1e18
 
ll n, a, b, l, r, res;
vector<pair<ll,ll>> v;
 
ll gcd(ll c1, ll c2) {
    if (!c2) return c1;
    return gcd(c2, c1%c2);
}
 
int main() {
    cin >> n >> a >> b;
    a = a/gcd(a, b+1);
    if ((double)a > (double)big+1/b){
        res = big+1;
    }
    else {
        res = a*b;
    }
    while (n--) {
        cin >> l >> r;
        l%=res;
        r%=res;
        if (l>r) v.push_back({0, r}), v.push_back({l, res-1});
        else v.push_back({l, r});
    }
    sort(v.begin(), v.end());
    ll fi=0, se=INT_MIN;
    for (ll i=0;i<v.size();i++){
        ll d1=v[i].first;
        ll d2=v[i].second;
        if(se<d1){
            fi+=d2-d1+1;
        }
        else{
            fi+=max((ll)0, d2-se);
        }
        se=max(se, d2);
    }
    cout << fi <<endl;;
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 1040 KB Output is correct
3 Correct 18 ms 1060 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 300 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 131 ms 5648 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 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 352 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 930 ms 19536 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 1324 ms 21876 KB Output is correct
3 Correct 1290 ms 39540 KB Output is correct
4 Correct 1297 ms 39560 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 1324 ms 21876 KB Output is correct
3 Correct 1290 ms 39540 KB Output is correct
4 Correct 1297 ms 39560 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1313 ms 39736 KB Output is correct
7 Correct 1304 ms 39476 KB Output is correct
8 Correct 1281 ms 39556 KB Output is correct
9 Correct 1441 ms 39520 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 1324 ms 21876 KB Output is correct
3 Correct 1290 ms 39540 KB Output is correct
4 Correct 1297 ms 39560 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 137 ms 5600 KB Output is correct
7 Correct 134 ms 5672 KB Output is correct
8 Correct 128 ms 5688 KB Output is correct
9 Correct 125 ms 5612 KB Output is correct
10 Correct 144 ms 5724 KB Output is correct
11 Correct 142 ms 5672 KB Output is correct
12 Correct 131 ms 5704 KB Output is correct
13 Correct 131 ms 5644 KB Output is correct
14 Correct 137 ms 5628 KB Output is correct
15 Correct 138 ms 5596 KB Output is correct
16 Correct 128 ms 5692 KB Output is correct
17 Correct 130 ms 5692 KB Output is correct
18 Correct 1332 ms 39556 KB Output is correct
19 Correct 1271 ms 39608 KB Output is correct
20 Correct 1355 ms 39624 KB Output is correct
21 Correct 177 ms 5604 KB Output is correct
22 Correct 129 ms 5676 KB Output is correct
23 Correct 432 ms 18476 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 133 ms 5688 KB Output is correct
3 Correct 135 ms 4808 KB Output is correct
4 Correct 1383 ms 21964 KB Output is correct
5 Correct 137 ms 5688 KB Output is correct
6 Correct 135 ms 5712 KB Output is correct
7 Correct 144 ms 5644 KB Output is correct
8 Correct 133 ms 5652 KB Output is correct
9 Correct 130 ms 5728 KB Output is correct
10 Correct 145 ms 5620 KB Output is correct
11 Correct 141 ms 5656 KB Output is correct
12 Correct 124 ms 5652 KB Output is correct
13 Correct 127 ms 5600 KB Output is correct
14 Correct 1366 ms 39524 KB Output is correct
15 Correct 135 ms 5584 KB Output is correct
16 Correct 1502 ms 39416 KB Output is correct
17 Correct 1322 ms 39416 KB Output is correct
18 Correct 1 ms 300 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 1040 KB Output is correct
3 Correct 18 ms 1060 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 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 300 KB Output is correct
9 Correct 1 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 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1032 KB Output is correct
17 Correct 131 ms 5648 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -