Submission #13303

#	Time	Username	Problem	Language	Result	Execution time	Memory
13303		baneling100	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	437 ms	134136 KiB

apple

#include <stdio.h>
#define INF 1073741824

struct node {
    node() : left(NULL), right(NULL), cnt(NULL), lazy(NULL) {}
    node *left, *right;
    int cnt, lazy;
} *Root;
int M, D, X, Y, C;

void countApple(int left, int right, node *now) {

    int mid=(left+right)/2;

    if(X<=left && right<=Y)
        C+=now->cnt;
    else {
        if(!now->left ) now->left =new node();
        if(!now->right) now->right=new node();
        if(now->lazy) {
            now->left ->cnt =mid-left+1;
            now->left ->lazy=1;
            now->right->cnt =right-mid;
            now->right->lazy=1;
        }
        if(X<=mid)   countApple(left ,mid  ,now->left );
        if(mid+1<=Y) countApple(mid+1,right,now->right);
        if(!now->lazy) {
            if(now->left->lazy && now->right->lazy) {
                now->cnt =right-left+1;
                now->lazy=1;
            }
            else now->cnt=now->left->cnt+now->right->cnt;
        }
    }
}

void ripeApple(int left, int right, node *now) {

    int mid=(left+right)/2;

    if(X<=left && right<=Y) {
        now->cnt =right-left+1;
        now->lazy=1;
    }
    else {
        if(!now->left ) now->left =new node();
        if(!now->right) now->right=new node();
        if(now->lazy) {
            now->left ->cnt =mid-left+1;
            now->left ->lazy=1;
            now->right->cnt =right-mid;
            now->right->lazy=1;
        }
        if(X<=mid)   ripeApple(left ,mid  ,now->left );
        if(mid+1<=Y) ripeApple(mid+1,right,now->right);
        if(!now->lazy) {
            if(now->left->lazy && now->right->lazy) {
                now->cnt =right-left+1;
                now->lazy=1;
            }
            else now->cnt=now->left->cnt+now->right->cnt;
        }
    }
}

int main(void) {

    int i;

    Root=new node();
    scanf("%d",&M);
    for(i=1 ; i<=M ; i++) {
        scanf("%d %d %d",&D,&X,&Y);
        X+=C, Y+=C;
        if(D==1) {
            C=0;
            countApple(1,INF,Root);
            printf("%d\n",C);
        }
        else
            ripeApple(1,INF,Root);
    }

    return 0;
}

• Subtask 1: 100 / 100