Submission #1018430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1018430	2024-07-10T04:00:24 Z	aufan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	282 ms	205704 KB

apple

#include <bits/stdc++.h>
// #define int long long
#define fi first
#define se second

using namespace std;

const int inf = 1e9;

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;
                lz = 0;
        }

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

                if (lz == 1) {
                        left->val = lz * left->len;
                        left->lz = lz;

                        right->val = lz * right->len;
                        right->lz = lz;
                }
        }

        int query(int lf, int rg) {
                if (st > rg || en < lf) return 0;
                if (lf <= st && en <= rg) return val;
                lazy();
                return left->query(lf, rg) + right->query(lf, rg);
        }

        void update(int lf, int rg) {
                if (st > rg || en < lf) return;
                if (lf <= st && en <= rg) {
                        val = 1 * len;
                        lz = 1;
                        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 q;
        cin >> q;

        int c = 0;
        sg.build(1, inf);
        for (int i = 0; i < q; i++) {
                int t, x, y;
                cin >> t >> x >> y;

                if (t == 1) {
                        int ans = sg.query(x + c, y + c);
                        cout << ans << '\n';
                        c = ans;
                } else if (t == 2) {
                        sg.update(x + c, y + c);
                }
        }
        
        return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	508 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	4780 KB	Output is correct
5	Correct	10 ms	5980 KB	Output is correct
6	Correct	10 ms	5724 KB	Output is correct
7	Correct	11 ms	5980 KB	Output is correct
8	Correct	79 ms	43684 KB	Output is correct
9	Correct	161 ms	75600 KB	Output is correct
10	Correct	179 ms	83540 KB	Output is correct
11	Correct	180 ms	89936 KB	Output is correct
12	Correct	184 ms	92756 KB	Output is correct
13	Correct	171 ms	107860 KB	Output is correct
14	Correct	165 ms	109104 KB	Output is correct
15	Correct	268 ms	199760 KB	Output is correct
16	Correct	271 ms	201040 KB	Output is correct
17	Correct	177 ms	112720 KB	Output is correct
18	Correct	171 ms	112720 KB	Output is correct
19	Correct	272 ms	205688 KB	Output is correct
20	Correct	282 ms	205704 KB	Output is correct