oj.uz

Submission #721776

# Submission time Handle Problem Language Result Execution time Memory
721776 2023-04-11T07:12:56 Z joelgun14 Strange Device (APIO19_strange_device) C++17
10 / 100
 662 ms 35284 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<ll, 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 {
            if(tot <= 1e18) {
                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;
        }
        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 6 ms 1240 KB Output is correct
3 Correct 6 ms 1240 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 0 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory 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 328 KB Output is correct
5 Correct 355 ms 33216 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 574 ms 35220 KB Output is correct
3 Incorrect 507 ms 35284 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 320 KB Output is correct
2 Correct 574 ms 35220 KB Output is correct
3 Incorrect 507 ms 35284 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 320 KB Output is correct
2 Correct 574 ms 35220 KB Output is correct
3 Incorrect 507 ms 35284 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 59 ms 5784 KB Output is correct
3 Correct 66 ms 5376 KB Output is correct
4 Correct 662 ms 33396 KB Output is correct
5 Correct 63 ms 5572 KB Output is correct
6 Correct 65 ms 5440 KB Output is correct
7 Correct 63 ms 5560 KB Output is correct
8 Correct 59 ms 5468 KB Output is correct
9 Correct 57 ms 5608 KB Output is correct
10 Correct 62 ms 5440 KB Output is correct
11 Correct 57 ms 5636 KB Output is correct
12 Correct 55 ms 5500 KB Output is correct
13 Correct 76 ms 5564 KB Output is correct
14 Correct 614 ms 33296 KB Output is correct
15 Incorrect 60 ms 5568 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 6 ms 1240 KB Output is correct
3 Correct 6 ms 1240 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -