oj.uz

답안 #258393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258393 2020-08-05T21:20:44 Z DS007 이상한 기계 (APIO19_strange_device) C++14
35 / 100
 904 ms 33348 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a, b;

bool overflow(int x, int y) {
    int result = x * y;
    return result / x != y;
}

int sum() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ans += r - l + 1;
    }
    return ans;
}

int solveTestCase() {
    cin >> n >> a >> b;

    int temp = a / __gcd(a, b + 1);
    assert(a % __gcd(a, b + 1) == 0);
    if (overflow(temp, b))
        return cout << sum(), 0;

    temp *= b;
    //cerr << temp << "\n";
    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;

        if (r - l + 1 >= temp)
            return cout << temp, 0;

        if (l % temp <= r % temp)
            v.emplace_back(l % temp, 1), v.emplace_back(r % temp + 1, 2);
        else
            v.emplace_back(l % temp, 1), v.emplace_back(temp, 2), v.emplace_back(0, 1), v.emplace_back(r % temp + 1, 2);
    }

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

    int ans = 0, d = 0, last = 0;
    for (auto i : v) {
        if (d == 0)
            last = i.first;

        if (i.second == 1)
            d++;
        else
            d--;

        assert(d >= 0);
        if (d == 0)
            ans += i.first - last;
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

strange_device.cpp: In function 'long long int solveTestCase()':
strange_device.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 6 ms 1024 KB Output is correct
3 Correct 7 ms 1024 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 6 ms 1024 KB Output is correct
17 Correct 73 ms 4588 KB Output is correct
18 Incorrect 0 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 Incorrect 0 ms 384 KB Output isn't correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 416 ms 33248 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 624 ms 33348 KB Output is correct
3 Correct 654 ms 33344 KB Output is correct
4 Correct 625 ms 33344 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 613 ms 33336 KB Output is correct
7 Correct 615 ms 33344 KB Output is correct
8 Correct 635 ms 33304 KB Output is correct
9 Correct 748 ms 33344 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 624 ms 33348 KB Output is correct
3 Correct 654 ms 33344 KB Output is correct
4 Correct 625 ms 33344 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 60 ms 4588 KB Output is correct
7 Correct 65 ms 4616 KB Output is correct
8 Correct 56 ms 4588 KB Output is correct
9 Correct 58 ms 4588 KB Output is correct
10 Correct 58 ms 4596 KB Output is correct
11 Correct 60 ms 4596 KB Output is correct
12 Correct 70 ms 4580 KB Output is correct
13 Correct 68 ms 4588 KB Output is correct
14 Correct 62 ms 4596 KB Output is correct
15 Correct 71 ms 4588 KB Output is correct
16 Correct 88 ms 4592 KB Output is correct
17 Correct 58 ms 4588 KB Output is correct
18 Correct 647 ms 33344 KB Output is correct
19 Correct 609 ms 33348 KB Output is correct
20 Correct 797 ms 33312 KB Output is correct
21 Correct 72 ms 4588 KB Output is correct
22 Correct 53 ms 4712 KB Output is correct
23 Correct 183 ms 16980 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 69 ms 4588 KB Output is correct
3 Correct 75 ms 4580 KB Output is correct
4 Correct 812 ms 33348 KB Output is correct
5 Correct 68 ms 4588 KB Output is correct
6 Correct 68 ms 4584 KB Output is correct
7 Correct 66 ms 4740 KB Output is correct
8 Correct 72 ms 4588 KB Output is correct
9 Correct 67 ms 4588 KB Output is correct
10 Correct 73 ms 4584 KB Output is correct
11 Correct 65 ms 4588 KB Output is correct
12 Correct 62 ms 4588 KB Output is correct
13 Correct 67 ms 4596 KB Output is correct
14 Correct 904 ms 33264 KB Output is correct
15 Correct 77 ms 4584 KB Output is correct
16 Correct 594 ms 33348 KB Output is correct
17 Correct 627 ms 33344 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 6 ms 1024 KB Output is correct
3 Correct 7 ms 1024 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 6 ms 1024 KB Output is correct
17 Correct 73 ms 4588 KB Output is correct
18 Incorrect 0 ms 384 KB Output isn't correct