Submission #378062

#	Time	Username	Problem	Language	Result	Execution time	Memory
378062		rqi	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	243 ms	3180 KiB

apple

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

struct Node{
    int L, R;
    Node* c[2];
    bool active;
    int sum;
    Node(int _L, int _R){
        L = _L; R = _R;
        c[0] = NULL; c[1] = NULL;
        active = 0;
        sum = 0;
    }
};

int getSum(Node* node){
    if(!node) return 0;
    return node->sum;
}

void makeActive(Node* node){
    if(!node->active){
        node->active = 1;
        node->sum = (node->R)-(node->L)+1;
    }
}

void pull(Node* node){
    if(node->active) return;
    node->sum = getSum(node->c[0])+getSum(node->c[1]);
}

void upd(Node* node, int l, int r){
    if(node->active) return;

    int L = node->L;
    int R = node->R;
    int M = (L+R)/2;

    if(R < l || r < L) return;

    if(l <= L && R <= r){
        makeActive(node);
        //cout << "makeActive: " << L << " " << R << "\n";
        return;
    }

    if(!node->c[0]){
        node->c[0] = new Node(L, M);
    }
    if(!node->c[1]){
        node->c[1] = new Node(M+1, R);
    }

    upd(node->c[0], l, r); upd(node->c[1], l, r);

    pull(node);
}

int query(Node* node, int l, int r){
    int L = node->L;
    int R = node->R;
    //cout << L << " " << R << "\n";

    if(R < l || r < L) return 0;
    if(l <= L && R <= r){
        //cout << L << " " << R << " " << node->sum << "\n";
        return node->sum;
    }

    if(node->active){
        return min(r, R)-max(l, L)+1;
    }

    int res = 0;
    if(node->c[0]){
        res+=query(node->c[0], l, r);
    }
    if(node->c[1]){
        res+=query(node->c[1], l, r);
    }
    return res;
}



int main(){
    int M;
    cin >> M;
    int C = 0;

    Node* seg = new Node(1, 1e9);

    for(int i = 1; i <= M; i++){
        int D, X, Y;
        cin >> D >> X >> Y;
        X+=C;
        Y+=C;
        if(D == 1){
            int res = query(seg, X, Y);
            cout << res << "\n";
            C = res;
        }
        else{
            upd(seg, X, Y);
        }
    }
}

• Subtask 1: 100 / 100