oj.uz

답안 #264028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
264028 2020-08-14T04:49:52 Z batmendbar 이상한 기계 (APIO19_strange_device) C++14
10 / 100
 494 ms 28064 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<int, int> > 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));
        }
    }
    sort (v.begin(), v.end());
    long long bg = 0, en = -1;
    for (pair<int, int> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 348 ms 16608 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 454 ms 28008 KB Output is correct
3 Incorrect 494 ms 28064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 454 ms 28008 KB Output is correct
3 Incorrect 494 ms 28064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 454 ms 28008 KB Output is correct
3 Incorrect 494 ms 28064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 65 ms 4976 KB Output is correct
3 Incorrect 61 ms 5020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -