Submission #1018430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018430		aufan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	282 ms	205704 KiB

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 / 100