Submission #918418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918418	2024-01-29T19:48:34 Z	asdasdqwer	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	246 ms	262144 KB

apple

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

#define int int64_t

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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	9424 KB	Output is correct
5	Correct	12 ms	10752 KB	Output is correct
6	Correct	12 ms	8912 KB	Output is correct
7	Correct	12 ms	9520 KB	Output is correct
8	Correct	98 ms	67488 KB	Output is correct
9	Correct	226 ms	133012 KB	Output is correct
10	Correct	226 ms	135056 KB	Output is correct
11	Correct	224 ms	134748 KB	Output is correct
12	Correct	233 ms	134612 KB	Output is correct
13	Correct	207 ms	135036 KB	Output is correct
14	Correct	187 ms	134756 KB	Output is correct
15	Runtime error	246 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-