Submission #18612

#	Time	Username	Problem	Language	Result	Execution time	Memory
18612		mindol	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	676 ms	260324 KiB

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 / 100