제출 #1368671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368671		tranvinhhuy2010	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	128 ms	63504 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int adu = 4e6 + 5;

struct node {
    int left, right, sum;
    bool lz;
} st[adu];

int num = 0;
int new_node() {
    num++;
    st[num].left = st[num].right = st[num].sum = 0;
    st[num].lz = false;
    return num;
}

void push_down(int id, int l, int r) {
    if (!st[id].lz) return;

    int mid = (l + r) / 2;
    if (!st[id].left) st[id].left = new_node();
    if (!st[id].right) st[id].right = new_node();

    int lc = st[id].left, rc = st[id].right;
    st[lc].sum = mid - l + 1, st[lc].lz = true;
    st[rc].sum = r - mid, st[rc].lz = true;

    st[id].lz = false;
}

void update(int& id, int l, int r, int ql, int qr) {
    if (l>qr || r<ql) return;

    if (!id) id = new_node();
    if (ql<=l && r<=qr) {
        st[id].sum = r - l + 1;
        st[id].lz = true;
        return;
    }

    push_down(id, l, r);

    int mid = (l + r) / 2;
    update(st[id].left, l, mid, ql, qr);
    update(st[id].right, mid + 1, r, ql, qr);

    st[id].sum = st[st[id].left].sum + st[st[id].right].sum;
}

int get(int id, int l, int r, int ql, int qr) {
    if (!id || l>qr || r<ql) return 0;
    if (ql<=l && r<=qr) return st[id].sum;

    push_down(id, l, r);

    int mid = (l + r) / 2;
    return get(st[id].left, l, mid, ql, qr) + get(st[id].right, mid + 1, r, ql, qr);
}

int m;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m;

    int root = new_node(), c = 0;

    while (m--) {
        int d, x, y; cin >> d >> x >> y;

        if (d==1) {
            c = get(root, 1, 1e9, x + c, y + c);
            cout << c << '\n';
        }
        else update(root, 1, 1e9, x + c, y + c);
    }

    return 0;
}

• 서브태스크 1: 0 / 100