Submission #18612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18612	2016-02-11T12:23:01 Z	mindol	Monkey and Apple-trees (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

#	Verdict	Execution time	Memory	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