제출 #1188634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188634		sonya	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	2094 ms	33484 KiB

apple

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int cl = 0, cr = 0;
    long long sum = 0;
};

vector<Node> tree(2);
int next_node = 2;
const int MAX = 1e9;

void create(int h) {
    if (tree[h].cl == 0) {
        tree[h].cl = next_node++;
        tree[h].cr = next_node++;
        if ((int)tree.size() <= next_node + 2) tree.resize(next_node + 10);
    }
}

void update(int node, int l, int r, int ul, int ur) {
    if (r < ul || l > ur) return;
    if (l == r) {
        tree[node].sum = 1;
        return;
    }

    create(node);
    int mid = (l + r) / 2;
    update(tree[node].cl, l, mid, ul, ur);
    update(tree[node].cr, mid + 1, r, ul, ur);
    tree[node].sum = tree[tree[node].cl].sum + tree[tree[node].cr].sum;
}

long long query(int node, int l, int r, int ql, int qr) {
    if (node == 0 || r < ql || l > qr) return 0;
    if (ql <= l && r <= qr) return tree[node].sum;

    create(node);
    int mid = (l + r) / 2;
    return query(tree[node].cl, l, mid, ql, qr) + query(tree[node].cr, mid + 1, r, ql, qr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("f.in", "r", stdin);
    // freopen("f.out", "w", stdout);

    int M;
    cin >> M;
    long long C = 0;

    for (int i = 0; i < M; ++i) {
        int D, X, Y;
        cin >> D >> X >> Y;

        int l = X + C;
        int r = Y + C;

        if (l > r) swap(l, r);

        if (D == 1) {
            long long res = query(1, 1, MAX, l, r);
            cout << res << '\n';
            C = res;
        } else {
            update(1, 1, MAX, l, r);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100