oj.uz

Submission #721730

# Submission time Handle Problem Language Result Execution time Memory
721730 2023-04-11T06:52:50 Z joelgun14 Strange Device (APIO19_strange_device) C++17
10 / 100
 846 ms 66968 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, int>> 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;
        }
        else {
            // start
            // start itu + cnt
            // set start kalo belum di set
            if(cnt == 0)
                st = i.first - 1;
            ++cnt;
        }
    }
    cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 9 ms 1748 KB Output is correct
3 Correct 10 ms 1748 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 429 ms 66160 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 667 ms 66968 KB Output is correct
3 Incorrect 632 ms 66804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 667 ms 66968 KB Output is correct
3 Incorrect 632 ms 66804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 667 ms 66968 KB Output is correct
3 Incorrect 632 ms 66804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 9140 KB Output is correct
3 Correct 74 ms 8784 KB Output is correct
4 Correct 817 ms 66128 KB Output is correct
5 Correct 77 ms 8888 KB Output is correct
6 Correct 77 ms 8960 KB Output is correct
7 Correct 65 ms 8948 KB Output is correct
8 Correct 71 ms 8952 KB Output is correct
9 Correct 66 ms 8896 KB Output is correct
10 Correct 70 ms 8880 KB Output is correct
11 Correct 63 ms 8948 KB Output is correct
12 Correct 65 ms 8912 KB Output is correct
13 Correct 84 ms 8880 KB Output is correct
14 Correct 846 ms 66172 KB Output is correct
15 Incorrect 104 ms 8876 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 9 ms 1748 KB Output is correct
3 Correct 10 ms 1748 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -