Submission #500749

#	Time	Username	Problem	Language	Result	Execution time	Memory
500749		Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	424 ms	262148 KiB

apple

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

class SegmentTree {
    public :
        int tree, lazy;
        int l, r;
        SegmentTree *L, *R;
        SegmentTree() {}
        SegmentTree(int left, int right) {
            tree = lazy = 0;
            l = left;
            r = right;
            L = R = NULL;
        }
};

void compute(SegmentTree *now) {
    int mid = (now->l + now->r) / 2;
    if(now->L == NULL) {
        now->L = new SegmentTree(now->l, mid);
    }
    if(now->R == NULL) {
        now->R = new SegmentTree(mid + 1, now->r);
    }
}

void push_lazy(SegmentTree *now) {
    if(!now->lazy) {
        return;
    }

    now->tree = now->r - now->l + 1;
    compute(now);
    if(now->l != now->r) {
        now->L->lazy = now->R->lazy = 1;
    }

    now->lazy = 0;
}

void update(SegmentTree *now, int ql, int qr) {
    push_lazy(now);
    if(now->r < ql || qr < now->l) {
        return;
    }
    if(ql <= now->l && now->r <= qr) {
        now->lazy = 1;
        push_lazy(now);
        return;
    }

    compute(now);
    update(now->L, ql, qr);
    update(now->R, ql, qr);
    now->tree = now->L->tree + now->R->tree;
}

int query(SegmentTree *now, int ql, int qr) {
    push_lazy(now);
    if(now->r < ql || qr < now->l) {
        return 0;
    }
    if(ql <= now->l && now->r <= qr) {
        return now->tree;
    }

    compute(now);
    return query(now->L, ql, qr) + query(now->R, ql, qr);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m;
    cin >> m;
    int C = 0;
    SegmentTree *root = new SegmentTree(1, 1e9);
    while(m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 2) {
            update(root, x + C, y + C);
        }
        else {
            C = query(root, x + C, y + C);
            cout << C << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 100