oj.uz

Submission #783426

# Submission time Handle Problem Language Result Execution time Memory
783426 2023-07-14T23:13:53 Z christinelynn Strange Device (APIO19_strange_device) C++17
10 / 100
 604 ms 73892 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 2e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, a, b;
        cin >> n >> a >> b;

        /*
        0 0 0 0
        1 1 1 1
        2 2 2 2
        4 3 1 0
        5 4 2 1
        6 5 0 2
        8 6 2 0
        9 7 0 1
        10 8 1 2
        12 9 0 0
        */

        set<pair<int, int>> seg;
        
        auto insert = [&](int l, int r) {
                auto it = seg.lower_bound({l, 0});
                if (it != seg.begin()) --it;

                int mnl = l, mxr = r;
                vector<pair<int, int>> del;

                for (; it != seg.end(); it++) {
                        if (it->fi > r) break;

                        if (it->fi < l && it->se >= l) {
                                del.push_back(*it);
                                mnl = min(mnl, it->fi);
                                mxr = max(mxr, it->se);
                        }

                        if (it->fi >= l && it->fi <= r) {
                                del.push_back(*it);
                                mnl = min(mnl, it->fi);
                                mxr = max(mxr, it->se);
                        }
                }

                for (auto p : del) seg.erase(p);

                seg.insert({mnl, mxr});
        };

        for (int i = 0; i < n; i++) {
                int l, r;
                cin >> l >> r;

                if (a <= INFF / b && r - l + 1 >= a * b) {
                        cout << a * b << '\n';
                        return 0;
                }
                
                if (a <= INFF / b) {
                        l %= a * b;
                        r %= a * b;
                }

                if (l <= r) {
                        insert(l, r);
                } else {
                        assert(a <= INFF / b);

                        insert(l, a * b - 1);
                        insert(0, r);
                }
        }
        
        int ans = 0;
        for (auto [l, r] : seg) ans += r - l + 1;

        cout << ans << '\n';

        return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 1224 KB Output is correct
3 Correct 5 ms 1236 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 212 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 320 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 261 ms 796 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 535 ms 63768 KB Output is correct
3 Incorrect 604 ms 73708 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 535 ms 63768 KB Output is correct
3 Incorrect 604 ms 73708 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 535 ms 63768 KB Output is correct
3 Incorrect 604 ms 73708 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 49 ms 6800 KB Output is correct
3 Correct 53 ms 6860 KB Output is correct
4 Correct 536 ms 73724 KB Output is correct
5 Correct 51 ms 10176 KB Output is correct
6 Correct 52 ms 10232 KB Output is correct
7 Correct 60 ms 10188 KB Output is correct
8 Correct 57 ms 10156 KB Output is correct
9 Correct 55 ms 10260 KB Output is correct
10 Correct 44 ms 10168 KB Output is correct
11 Correct 46 ms 10208 KB Output is correct
12 Correct 47 ms 10188 KB Output is correct
13 Correct 51 ms 10188 KB Output is correct
14 Correct 580 ms 73892 KB Output is correct
15 Incorrect 49 ms 10220 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 5 ms 1224 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -