oj.uz

Submission #721549

# Submission time Handle Problem Language Result Execution time Memory
721549 2023-04-11T04:11:08 Z joelgun14 Strange Device (APIO19_strange_device) C++17
10 / 100
 864 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;
    for(int i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        if(r - l >= (lll)1 * a * b) {
            ans = (lll)1 * a * b;
        }
        else {
            l %= (lll)1 * a * b;
            r %= (lll)1 * a * b;
            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((lll)a * b - 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:51:32: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |                 ans += i.first - st;
      |                        ~~~~~~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 1492 KB Output is correct
3 Correct 9 ms 1492 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 340 KB Output is correct
5 Correct 406 ms 66004 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 569 ms 66040 KB Output is correct
3 Incorrect 512 ms 66012 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 569 ms 66040 KB Output is correct
3 Incorrect 512 ms 66012 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 569 ms 66040 KB Output is correct
3 Incorrect 512 ms 66012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 61 ms 8572 KB Output is correct
3 Correct 78 ms 8548 KB Output is correct
4 Correct 755 ms 66036 KB Output is correct
5 Correct 60 ms 8596 KB Output is correct
6 Correct 68 ms 8576 KB Output is correct
7 Correct 63 ms 8576 KB Output is correct
8 Correct 66 ms 8636 KB Output is correct
9 Correct 58 ms 8648 KB Output is correct
10 Correct 69 ms 8656 KB Output is correct
11 Correct 61 ms 8648 KB Output is correct
12 Correct 53 ms 8648 KB Output is correct
13 Correct 68 ms 8648 KB Output is correct
14 Correct 864 ms 66104 KB Output is correct
15 Incorrect 68 ms 8636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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