oj.uz

Submission #783419

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

using namespace std;

const int INFF = 2e18;

struct node {
        int val, lz;
        int st, en, len;
        node *left, *right;

        void build(int start, int end) {
                st = start;
                en = end;
                len = en - st + 1;
                val = 0;
                lz = 0;
        }

        void lazy() {
                if (left == NULL && right == NULL) {
                        left = new node();
                        right = new node();
                        int md = (st + en) / 2;
                        left->build(st, md);
                        right->build(md + 1, en);
                }
                if (lz == 1) {
                        left->lz = lz;
                        left->val = lz * left->len;
                        right->lz = lz;
                        right->val = lz * right->len;
                        lz = 0;
                }
        }

        void update(int lf, int rg) {
                if (st > rg || en < lf) return;
                if (lf <= st && en <= rg) {
                        lz = 1;
                        val = len;
                        return;
                }
                lazy();
                left->update(lf, rg);
                right->update(lf, rg);
                val = left->val + right->val;
        }
} sg;
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
        */

        if (a > INFF / b) {
                sg.build(0, INFF);
        } else {
                sg.build(0, a * b - 1);
        }

        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) {
                        // cout << l << " " << r << '\n';
                        sg.update(l, r);
                } else {
                        // cout << l << " " << a * b - 1 << '\n';
                        sg.update(l, a * b - 1);
                        // cout << 0 << " " << r << '\n';
                        sg.update(0, r);
                }
        }

        cout << sg.val << '\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 8 ms 5836 KB Output is correct
3 Correct 10 ms 6868 KB Output is correct
4 Incorrect 0 ms 340 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 324 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 2 ms 1872 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 287 ms 744 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 463 ms 126568 KB Output is correct
3 Runtime error 611 ms 524288 KB Execution killed with signal 9
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 463 ms 126568 KB Output is correct
3 Runtime error 611 ms 524288 KB Execution killed with signal 9
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 463 ms 126568 KB Output is correct
3 Runtime error 611 ms 524288 KB Execution killed with signal 9
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 125 ms 88192 KB Output is correct
3 Correct 212 ms 201068 KB Output is correct
4 Runtime error 514 ms 524288 KB Execution killed with signal 9
5 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 8 ms 5836 KB Output is correct
3 Correct 10 ms 6868 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -