답안 #18612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18612	2016-02-11T12:23:01 Z	mindol	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	676 ms	260324 KB

apple

#include<cstdio>

struct Node
{
    int value = 0; bool lazy = false;
    Node *left = nullptr, *right = nullptr;
};

void lazydown(Node *now,int now_l,int now_r)
{
    if(!now->lazy) return;

    now->value = now_r-now_l+1;
    now->lazy = false;

    if(now_l==now_r) return;

    if(now->left == nullptr) now->left = new Node();
    now->left->lazy = true;
    if(now->right == nullptr) now->right = new Node();
    now->right->lazy = true;
}

void check(int l,int r,Node *now,int now_l,int now_r)
{
    lazydown(now,now_l,now_r);
    if(now_l>r || now_r<l) return;
    else if(l<=now_l && now_r<=r) now->lazy = true, lazydown(now,now_l,now_r);
    else
    {
        int mid=(now_l+now_r)/2;
        if(now->left == nullptr) now->left = new Node();
        if(now->right == nullptr) now->right = new Node();
        check(l,r,now->left,now_l,mid);
        check(l,r,now->right,mid+1,now_r);
        now->value = now->left->value + now->right->value;
    }
}

int rangeSum(int l,int r,Node *now,int now_l,int now_r)
{
    lazydown(now,now_l,now_r);
    if(now_l>r || now_r<l) return 0;
    else if(l<=now_l && now_r<=r) return now->value;
    else
    {
        int mid=(now_l+now_r)/2;
        if(now->left == nullptr) now->left = new Node();
        if(now->right == nullptr) now->right = new Node();
        return rangeSum(l,r,now->left,now_l,mid)+rangeSum(l,r,now->right,mid+1,now_r);
    }
}

int main()
{
    int m;
    scanf("%d",&m);
    int C=0;

    Node *root = new Node();
    while(m--)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if(a==1) printf("%d\n",C=rangeSum(b+C,c+C,root,1,1e9));
        else check(b+C,c+C,root,1,1e9);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1208 KB	Output is correct
2	Correct	0 ms	1208 KB	Output is correct
3	Correct	0 ms	1208 KB	Output is correct
4	Correct	22 ms	6620 KB	Output is correct
5	Correct	25 ms	7808 KB	Output is correct
6	Correct	27 ms	7544 KB	Output is correct
7	Correct	34 ms	7808 KB	Output is correct
8	Correct	224 ms	52028 KB	Output is correct
9	Correct	377 ms	87800 KB	Output is correct
10	Correct	419 ms	98492 KB	Output is correct
11	Correct	427 ms	106676 KB	Output is correct
12	Correct	398 ms	110372 KB	Output is correct
13	Correct	422 ms	137036 KB	Output is correct
14	Correct	396 ms	138356 KB	Output is correct
15	Correct	662 ms	252272 KB	Output is correct
16	Correct	676 ms	254252 KB	Output is correct
17	Correct	450 ms	143372 KB	Output is correct
18	Correct	483 ms	143504 KB	Output is correct
19	Correct	639 ms	260192 KB	Output is correct
20	Correct	618 ms	260324 KB	Output is correct