oj.uz

Submission #153892

# Submission time Handle Problem Language Result Execution time Memory
153892 2019-09-17T11:02:36 Z DystoriaX Strange Device (APIO19_strange_device) C++14
0 / 100
 624 ms 18636 KB 
#include <bits/stdc++.h>

using namespace std;

int n;
long long a, b;
unsigned long long mx;
vector<pair<long long, long long> > seg;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    scanf("%d%lld%lld", &n, &a, &b);

    mx = a / gcd(a, b + 1);

    if(log10l(mx) + log10l(b) > 18){
        mx = 1e18;
    } else mx *= b;

    for(int i = 0; i < n; i++){
        long long l, r;
        scanf("%lld%lld", &l, &r);

        l %= mx, r %= mx;

        if(r - l + 1 >= mx){
            seg.emplace_back(0, mx - 1);
        } else if (l <= r){
            seg.emplace_back(l, r);
        } else {
            seg.emplace_back(l, mx - 1);
            seg.emplace_back(0, r);
        }
    }

    sort(seg.begin(), seg.end());

    long long ans = 0, last = 0;

    for(auto k : seg){
        ans += max(0LL, k.second - max(last, k.first) + 1);
        last = max(last, k.second + 1);
    }

    printf("%lld\n", ans);
    
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(r - l + 1 >= mx){
            ~~~~~~~~~~^~~~~
strange_device.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld%lld", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Incorrect 8 ms 1016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 579 ms 18636 KB Output is correct
3 Incorrect 552 ms 17508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 579 ms 18636 KB Output is correct
3 Incorrect 552 ms 17508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 579 ms 18636 KB Output is correct
3 Incorrect 552 ms 17508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 65 ms 3048 KB Output is correct
3 Correct 65 ms 3120 KB Output is correct
4 Correct 624 ms 17860 KB Output is correct
5 Correct 64 ms 3308 KB Output is correct
6 Correct 62 ms 3308 KB Output is correct
7 Correct 61 ms 3560 KB Output is correct
8 Correct 63 ms 3312 KB Output is correct
9 Correct 60 ms 3024 KB Output is correct
10 Correct 60 ms 2952 KB Output is correct
11 Correct 62 ms 3056 KB Output is correct
12 Incorrect 53 ms 3064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Incorrect 8 ms 1016 KB Output isn't correct
4 Halted 0 ms 0 KB -