Submission #340699

#	Time	Username	Problem	Language	Result	Execution time	Memory
340699		juggernaut	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	592 ms	207908 KiB

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