oj.uz

Submission #264067

# Submission time Handle Problem Language Result Execution time Memory
264067 2020-08-14T04:57:14 Z batmendbar Strange Device (APIO19_strange_device) C++14
5 / 100
 402 ms 16888 KB 
#include<bits/stdc++.h>
using namespace std;

const long long N = ((long long) 1e18) + 5;

long long gcd(long long x, long long y) {
    if (x < y) swap(x, y);
    while (y) {
        x %= y;
        swap(x, y);
    }
    return x;
}

vector< pair<long long, long long> > v;

long long ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, a, b;
    cin >> n >> a >> b;
    long long aa = a / gcd(a, b + 1);
    long long len;
    if (aa > (N / b)) 
        len = N;
    else len = a * b;
    for (int i = 0; i < n; i++) {
        long long bg, en;
        cin >> bg >> en;
        if (en - bg >= len) {
            cout << len << '\n';
            exit(0);
        }
        bg %= len;
        en %= len;
        if (bg > en) {
            v.push_back(make_pair(bg, len - 1));
            v.push_back(make_pair(0, en));
        } else {
            v.push_back(make_pair(bg, en));
        }
    }

    long long bg = 0, en = -1;
    for (pair<long long, long long> x : v) {
        long long bgg = x.first;
        long long enn = x.second;
        if (bgg > en) {
            ans += en - bg + 1;
            bg = bgg;
            en = enn;
            continue;
        }
        if (bgg <= en) {
            en = max(en, enn);
        }
    }
    ans += en - bg + 1;
    cout << ans << '\n';
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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