Submission #918424

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918424	2024-01-29T19:54:12 Z	asdasdqwer	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	285 ms	135332 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int sum = 0;
    int lIdx = -1;
    int rIdx = -1;
    int upd = 0;
};

struct Segtree {
    int n = 1<<30;
    vector<Node> seg;

    Segtree(int sjkd) {
        Node n1;
        seg = {n1};
    }

    void gen(int idx) {
        Node n1;
        seg.push_back(n1);
        seg.push_back(n1);
        seg[idx].lIdx = seg.size() - 2;
        seg[idx].rIdx = seg.size() - 1;
    }

    void pushdown(int idx, int l, int r) {
        if (seg[idx].upd == 0) {
            return;
        }

        int len = (r-l)/2;

        seg[seg[idx].lIdx].sum = seg[seg[idx].rIdx].sum = len;
        seg[seg[idx].lIdx].upd = seg[seg[idx].rIdx].upd = seg[idx].upd;

        seg[idx].upd = 0;
    }

    int get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return 0;
        if (rx - lx == 1) {
            return seg[x].sum;
        }

        if (seg[x].lIdx == -1) {
            gen(x);
            seg[seg[x].lIdx].sum = seg[seg[x].rIdx].sum = seg[x].sum / 2;
        }

        pushdown(x, lx, rx);

        if (lx >= l && rx <= r) {
            return seg[x].sum;
        }

        int m=(lx+rx)/2;

        return get(l, r, seg[x].lIdx, lx, m) + get(l, r, seg[x].rIdx, m, rx);
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, n);
    }

    void set(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;
        if (rx - lx == 1) {
            seg[x].sum = 1;
            return;
        }

        if (seg[x].lIdx == -1) {
            gen(x);
            seg[seg[x].lIdx].sum = seg[seg[x].rIdx].sum = seg[x].sum / 2;
        }

        pushdown(x, lx, rx);

        if (lx >= l && rx <= r) {
            seg[x].sum = rx-lx;
            seg[x].upd = 1;
            return;
        }

        int m=(lx+rx)/2;
        set(l, r, seg[x].lIdx, lx, m);
        set(l, r, seg[x].rIdx, m, rx);

        seg[x].sum = seg[seg[x].lIdx].sum + seg[seg[x].rIdx].sum;
    }

    void set(int l, int r) {
        set(l, r, 0, 0, n);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;cin>>m;
    int c=0;

    Segtree sg(45);

    while (m--) {
        int code;cin>>code;
        int x,y;cin>>x>>y;
        if (code == 1) {
            x += c;y += c;
            int ans = sg.get(x, y+1);
            cout<<ans<<"\n";
            c = ans;
        }

        else {
            x += c;y += c;
            sg.set(x, y+1);
        }
    }
}

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	1 ms	348 KB	Output is correct
4	Correct	9 ms	6356 KB	Output is correct
5	Correct	10 ms	4816 KB	Output is correct
6	Correct	16 ms	4820 KB	Output is correct
7	Correct	11 ms	6356 KB	Output is correct
8	Correct	71 ms	33888 KB	Output is correct
9	Correct	152 ms	66832 KB	Output is correct
10	Correct	158 ms	66728 KB	Output is correct
11	Correct	174 ms	66592 KB	Output is correct
12	Correct	177 ms	67432 KB	Output is correct
13	Correct	149 ms	68260 KB	Output is correct
14	Correct	147 ms	67804 KB	Output is correct
15	Correct	261 ms	135072 KB	Output is correct
16	Correct	238 ms	134300 KB	Output is correct
17	Correct	162 ms	69196 KB	Output is correct
18	Correct	149 ms	67960 KB	Output is correct
19	Correct	237 ms	135332 KB	Output is correct
20	Correct	285 ms	134812 KB	Output is correct