Submission #340699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340699	2020-12-28T08:24:38 Z	juggernaut	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	592 ms	207908 KB

apple

#include<bits/stdc++.h>
using namespace std;
int ql,qr;
struct node{
    int l,r,sum;
    bool flag;
    node *tl,*tr;
    node(int L,int R){
        tl=tr=NULL;
        l=L,r=R;
        sum=flag=0;
    }
};
void push(node *v){
    if(!v->flag)return;
    if(v->tl!=NULL)v->tl->flag|=v->flag;
    if(v->tr!=NULL)v->tr->flag|=v->flag;
    v->sum =(v->r-v->l+1);
}
void update(node *v){
    push(v);
    if(v->l>qr||v->r<ql)return;
    if(v->l>=ql&&v->r<=qr){
        v->flag=1;
        push(v);
        return;
    }
    int mid=(v->l+v->r)>>1;
    if(v->tl==NULL)v->tl=new node(v->l,mid);
    if(v->tr==NULL)v->tr=new node(mid+1,v->r);
    push(v);
    update(v->tl);
    update(v->tr);
    v->sum=v->tl->sum+v->tr->sum;
}
int get(node *v){
    if(ql>v->r||qr<v->l)return 0;
    push(v);
    if(qr>=v->r&&v->l>=ql)return v->sum;
    int mid=(v->l+v->r)>>1;
    if(v->tl==NULL)v->tl=new node(v->l,mid);
    if(v->tr==NULL)v->tr=new node(mid+1,v->r);
    push(v);
    return get(v->tl)+get(v->tr);
}
int main(){
    int res=0;
    node *root=new node(1,1e9+1);
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int test;
    cin>>test;
    while(test--){
        char type;
        cin>>type>>ql>>qr;
        ql+=res,qr+=res;
        if(type=='2')update(root);
        else cout<<(res=get(root))<<"\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	18 ms	5100 KB	Output is correct
5	Correct	23 ms	6124 KB	Output is correct
6	Correct	24 ms	5868 KB	Output is correct
7	Correct	22 ms	6124 KB	Output is correct
8	Correct	178 ms	44740 KB	Output is correct
9	Correct	370 ms	77440 KB	Output is correct
10	Correct	381 ms	85484 KB	Output is correct
11	Correct	434 ms	91936 KB	Output is correct
12	Correct	425 ms	94596 KB	Output is correct
13	Correct	389 ms	110164 KB	Output is correct
14	Correct	366 ms	111084 KB	Output is correct
15	Correct	577 ms	201708 KB	Output is correct
16	Correct	588 ms	203500 KB	Output is correct
17	Correct	381 ms	114924 KB	Output is correct
18	Correct	390 ms	114896 KB	Output is correct
19	Correct	592 ms	207764 KB	Output is correct
20	Correct	573 ms	207908 KB	Output is correct