Submission #348564

#	Time	Username	Problem	Language	Result	Execution time	Memory
348564		nicolaalexandra	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	857 ms	232796 KiB

apple

#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    int sum,lazy;
    segment_tree *left, *right;
    segment_tree (){
        left = right = NULL;
        sum = lazy = 0;
    }
};

segment_tree *rad;
int q,tip,x,y,sol,n,c;


void update_lazy (segment_tree *nod, int st, int dr){
    if (nod == NULL || !nod->lazy)
        return;

    if (st != dr){

        if (nod->left == NULL)
            nod->left = new segment_tree();
        if (nod->right == NULL)
            nod->right = new segment_tree();

        int mid = (st+dr)>>1;
        nod->left->sum = mid-st+1;
        nod->left->lazy = 1;

        nod->right->sum = dr-mid;
        nod->right->lazy = 1;
    }
    nod->lazy = 0;
}

void update (segment_tree *nod, int st, int dr, int x, int y){

    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){

        nod->sum = dr - st + 1;
        nod->lazy = 1;
        update_lazy (nod,st,dr);

        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid){
        if (nod->left == NULL)
            nod->left = new segment_tree();
        update (nod->left,st,mid,x,y);
    }

    if (y > mid){
        if (nod->right == NULL)
            nod->right = new segment_tree();
        update (nod->right,mid+1,dr,x,y);
    }

    nod->sum = 0;
    if (nod->left != NULL){
        update_lazy (nod->left,st,mid);
        nod->sum += nod->left->sum;
    }

    if (nod->right != NULL){
        update_lazy (nod->right,mid+1,dr);
        nod->sum += nod->right->sum;
    }

    //nod->sum = nod->left->sum + nod->right->sum;

}

void query (segment_tree *nod, int st, int dr, int x, int y){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        sol += nod->sum;
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid){
        //if (nod->left == NULL)
          //  nod->left = new segment_tree();
        if (nod->left != NULL)
            query (nod->left,st,mid,x,y);
    }
    if (y > mid){
        //if (nod->right == NULL)
          //  nod->right = new segment_tree();
        if (nod->right != NULL)
            query (nod->right,mid+1,dr,x,y);
    }

}



int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    rad = new segment_tree();
    n = 1000000000;

    cin>>q;
    c = 0;
    for (;q--;){
        cin>>tip>>x>>y;
        x += c, y += c;
        if (tip == 1){
            sol = 0;
            query (rad,1,n,x,y);
            cout<<sol<<"\n";

            c = sol;

        } else update (rad,1,n,x,y);
    }


    return 0;
}

• Subtask 1: 100 / 100