Submission #1018428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1018428	2024-07-10T03:53:21 Z	aufan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	300 ms	207768 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	8 ms	4956 KB	Output is correct
5	Correct	10 ms	5980 KB	Output is correct
6	Correct	10 ms	5756 KB	Output is correct
7	Correct	10 ms	5776 KB	Output is correct
8	Correct	78 ms	43856 KB	Output is correct
9	Correct	162 ms	75604 KB	Output is correct
10	Correct	174 ms	83792 KB	Output is correct
11	Correct	195 ms	89936 KB	Output is correct
12	Correct	187 ms	92752 KB	Output is correct
13	Correct	160 ms	107856 KB	Output is correct
14	Correct	157 ms	108880 KB	Output is correct
15	Correct	286 ms	201944 KB	Output is correct
16	Correct	280 ms	203348 KB	Output is correct
17	Correct	203 ms	114772 KB	Output is correct
18	Correct	162 ms	115024 KB	Output is correct
19	Correct	281 ms	207768 KB	Output is correct
20	Correct	300 ms	207680 KB	Output is correct