답안 #13303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13303 2015-02-11T14:35:52 Z baneling100 원숭이와 사과 나무 (IZhO12_apple) C++
100 / 100
437 ms 134136 KB
#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;
}
# 결과 실행 시간 메모리 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