Submission #783419

#	Time	Username	Problem	Language	Result	Execution time	Memory
783419		christinelynn	Strange Device (APIO19_strange_device)	C++17	10 / 100	611 ms	524288 KiB

strange_device

#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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30