Submission #13303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13303	2015-02-11T14:35:52 Z	baneling100	Monkey and Apple-trees (IZhO12_apple)	C++	100 / 100	437 ms	134136 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	10 ms	4116 KB	Output is correct
5	Correct	20 ms	4644 KB	Output is correct
6	Correct	20 ms	4512 KB	Output is correct
7	Correct	17 ms	4644 KB	Output is correct
8	Correct	124 ms	28668 KB	Output is correct
9	Correct	267 ms	50580 KB	Output is correct
10	Correct	295 ms	54012 KB	Output is correct
11	Correct	261 ms	58104 KB	Output is correct
12	Correct	318 ms	59952 KB	Output is correct
13	Correct	278 ms	70776 KB	Output is correct
14	Correct	294 ms	71436 KB	Output is correct
15	Correct	406 ms	130044 KB	Output is correct
16	Correct	437 ms	130968 KB	Output is correct
17	Correct	273 ms	73944 KB	Output is correct
18	Correct	286 ms	73944 KB	Output is correct
19	Correct	436 ms	134004 KB	Output is correct
20	Correct	429 ms	134136 KB	Output is correct