Submission #593385

#	Time	Username	Problem	Language	Result	Execution time	Memory
593385		karrigan	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	376 ms	262144 KiB

apple

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
struct node{
int l,r,next1,next2;
long long lazy,val;
node(){
next1=-1;
next2=-1;
lazy=0;
val=0;
}
};
vector<node>st;
void push(int t){
if (st[t].next1!=-1&&st[t].next2!=-1&&st[t].lazy!=0){
    int l=st[t].l,r=st[t].r;
    int mid=(l+r)/2;
    int lep=st[t].next1,rai=st[t].next2;
    st[lep].val=(mid-l+1);
    st[lep].lazy=1;
    st[rai].val=(r-mid);
    st[rai].lazy=1;
    st[t].lazy=0;
    return;
}
}
void update(int t,int l,int r){
    //cout<<l<<" "<<r<<" "<<st[t].l<<" "<<st[t].r<<'\n';
    if (st[t].l>r||st[t].r<l)return;
    if (l<=st[t].l&&st[t].r<=r){
        st[t].lazy=1;
        st[t].val=(st[t].r-st[t].l+1);
        return;
    }
    int mid=(st[t].l+st[t].r)/2;
    if (st[t].next1==-1&&st[t].next2==-1){
    st[t].next1=st.size();
    node fk;
    fk.l=st[t].l;
    fk.r=mid;
    st.push_back(fk);
    node ff;
    ff.l=mid+1;
    ff.r=st[t].r;
    st[t].next2=st.size();
    st.push_back(ff);
    }
    push(t);
    update(st[t].next1,l,r);
    update(st[t].next2,l,r);
    st[t].val=st[st[t].next1].val+st[st[t].next2].val;
}
long long query(int t,int l,int r,int u,int v){
    //cout<<u<<" "<<v<<" "<<st[t].l<<" "<<st[t].r<<" "<<st[t].val<<'\n';
    if (r<u||l>v)return 0;
    if (u<=l&&r<=v)return st[t].val;
   int mid=(st[t].l+st[t].r)/2;
    if (st[t].next1==-1&&st[t].next2==-1){
    st[t].next1=st.size();
    node fk;
    fk.l=st[t].l;
    fk.r=mid;
    st.push_back(fk);
    node ff;
    ff.l=mid+1;
    ff.r=st[t].r;
    st[t].next2=st.size();
    st.push_back(ff);
    }
    push(t);
    long long ans=query(st[t].next1,l,mid,u,v)+query(st[t].next2,mid+1,r,u,v);
    st[t].val=st[st[t].next1].val+st[st[t].next2].val;
    return ans;
}
int main()
{
    fastio
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int m;
    cin>>m;
    node temp;
    temp.l=1;
    temp.r=1e9;
    st.push_back(temp);
    long long c=0;
    for (int i=1;i<=m;i++){
       int z,x,y;
       cin>>z>>x>>y;
       x+=c;
       y+=c;
       if (z==1){
        c=query(0,1,1000000000,x,y);
        cout<<c<<'\n';
       }
       else {
        update(0,x,y);
       }
    }
}

• Subtask 1: 0 / 100