oj.uz

답안 #721564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721564 2023-04-11T04:24:37 Z joelgun14 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 857 ms 66104 KB 
#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define endl "\n"
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    // a or b has certain pattern
    // ab -> 1 cycle, no duplikat
    // next cycle: sama persis
    // maintain cycles in terms of ab, merge all segments
    // find modulo ab
    // exist more than one cycle long -> all possible
    // size ab berarti diff >= ab - 1
    vector<pair<lll, bool>> sweep;
    ll ans = -1;
    lll tot = (lll)a * b;
    for(int i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        if(r - l >= tot - 1) {
            ans = tot;
        }
        else {
            l = (l % tot);
            r = (r % tot);
            if(l <= r) {
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(r, 1));
            }
            else {
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(tot - 1, 1));
                sweep.push_back(make_pair(0, 0));
                sweep.push_back(make_pair(r, 1));
            }
        }
    }
    if(ans != -1)
        cout << ans << endl, exit(0);
    sort(sweep.begin(), sweep.end());
    int cnt = 0;
    ll st = -5;
    ans = 0;
    for(auto i : sweep) {
        if(i.second) {
            // end
            --cnt;
            if(cnt == 0)
                ans += i.first - st, st = i.first + 1;
        }
        else {
            // start
            // start itu + cnt
            // set start kalo belum di set
            if(cnt == 0)
                st = i.first - 1;
            ++cnt;
        }
        assert(cnt >= 0);
    }
    assert(cnt == 0);
    cout << ans << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 553 ms 66104 KB Output is correct
3 Incorrect 538 ms 66076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 553 ms 66104 KB Output is correct
3 Incorrect 538 ms 66076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 553 ms 66104 KB Output is correct
3 Incorrect 538 ms 66076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 68 ms 8628 KB Output is correct
3 Correct 63 ms 8580 KB Output is correct
4 Correct 857 ms 66104 KB Output is correct
5 Correct 60 ms 8648 KB Output is correct
6 Correct 60 ms 8672 KB Output is correct
7 Correct 62 ms 8648 KB Output is correct
8 Correct 70 ms 8648 KB Output is correct
9 Correct 62 ms 8580 KB Output is correct
10 Correct 68 ms 8664 KB Output is correct
11 Correct 60 ms 8668 KB Output is correct
12 Correct 51 ms 8648 KB Output is correct
13 Correct 61 ms 8664 KB Output is correct
14 Correct 715 ms 66080 KB Output is correct
15 Incorrect 66 ms 8656 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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