oj.uz

답안 #721550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721550 2023-04-11T04:13:07 Z joelgun14 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 790 ms 66156 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 %= tot;
            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(0, 0));
                sweep.push_back(make_pair(l, 0));
                sweep.push_back(make_pair(tot - 1, 1));
                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;
    ans = 0;
    for(auto i : sweep) {
        if(i.second) {
            // end
            --cnt;
            if(cnt == 0)
                ans += i.first - st;
        }
        else {
            // start
            // start itu + cnt
            // set start kalo belum di set
            if(cnt == 0)
                st = i.first - 1;
            ++cnt;
        }
    }
    cout << ans << endl;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:52:32: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |                 ans += i.first - st;
      |                        ~~~~~~~~^~~~

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 1 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 1 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 414 ms 66112 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 592 ms 65996 KB Output is correct
3 Incorrect 519 ms 66028 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 69 ms 8592 KB Output is correct
3 Correct 67 ms 8676 KB Output is correct
4 Correct 790 ms 66156 KB Output is correct
5 Correct 73 ms 8636 KB Output is correct
6 Correct 62 ms 8632 KB Output is correct
7 Correct 62 ms 8580 KB Output is correct
8 Correct 68 ms 8572 KB Output is correct
9 Correct 59 ms 8648 KB Output is correct
10 Correct 68 ms 8648 KB Output is correct
11 Correct 59 ms 8608 KB Output is correct
12 Correct 69 ms 8640 KB Output is correct
13 Correct 65 ms 8660 KB Output is correct
14 Correct 712 ms 65992 KB Output is correct
15 Incorrect 75 ms 8544 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 -