제출 #486369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486369		pannenkoek	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	202 ms	111812 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); i++)

using ll = long long;

int m;

struct Node{
    ll begin, end;
    bool ripe;
    Node *left, *right;

    Node(ll b, ll e){
        begin = b;
        end = e;
    }

    void ins(ll a, ll b){
        if(a <= begin && b >= end){
            ripe = true;
            return;
        } if(b < begin || a > end) return;

        if(left == NULL){
            ll mid = (begin + end) / 2;
            left = new Node(begin, mid);
            right = new Node(mid + 1, end);
        }
        left->ins(a, b);
        right->ins(a, b);
    }

    ll get(ll a, ll b){
        if(a > end || b < begin) return 0;
        if(ripe) {
            return min(end, b) - max(begin, a) + 1;
        } if(left == NULL){
            return 0;
        }
        return left->get(a, b) + right->get(a, b);
    }

} root(0, 1LL << 60);


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

    cin >> m;

    ll c = 0;
    rep(i, 0, m){
        ll d, x, y;
        cin >> d >> x >> y;

        x += c;
        y += c;

        if(d == 2){
            root.ins(x, y);
        } else {
            c = root.get(x, y);
            cout << c << "\n";
        }
    }
}

• Subtask 1: 100 / 100