Submission #1082628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082628		LeonidCuk	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	384 ms	188752 KiB

apple

#include <bits/stdc++.h>
using namespace std;
struct koce
{
    int sum=0,l=-1,r=-1,tl,tr,lazy=0;
};
int cnt=2;
vector<koce>st(64*123456);
void push_lazy(int i)
{
    if(st[i].lazy)
    {
        st[i].sum=st[i].tr-st[i].tl+1;
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        st[st[i].l].lazy=st[st[i].r].lazy=1;
        st[i].lazy=0;
    }
}
void  update(int i,int l,int r)
{
    push_lazy(i);
    if(st[i].tl==l&&st[i].tr==r)
    {
        st[i].lazy=1;
        push_lazy(i);
    }
    else
    {
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        if(l>m)update(st[i].r,l,r);
        else if(r<=m)update(st[i].l,l,r);
        else
        {
            update(st[i].l,l,m);
            update(st[i].r,m+1,r);
        }
        push_lazy(st[i].l);
        push_lazy(st[i].r);
        st[i].sum=st[st[i].l].sum+st[st[i].r].sum;
    }
}
int query(int i,int l,int r)
{
    push_lazy(i);
    if(st[i].tl==l&&st[i].tr==r)
    {
        return st[i].sum;
    }
    else
    {
        int m=(st[i].tl+st[i].tr)/2;
        if(st[i].l==-1)
        {
            st[i].l=cnt;
            cnt++;
            st[st[i].l].tl=st[i].tl;
            st[st[i].l].tr=m;
        }
        if(st[i].r==-1)
        {
            st[i].r=cnt;
            cnt++;
            st[st[i].r].tl=m+1;
            st[st[i].r].tr=st[i].tr;
        }
        if(l>m)return query(st[i].r,l,r);
        else if(r<=m)return query(st[i].l,l,r);
        else
        {
            return query(st[i].l,l,m)+query(st[i].r,m+1,r);
        }
    }
}
int main()
{
    int n,c=0,a,b,q;
    cin>>n;
    st[1].sum = 0;
	st[1].lazy = 0;
	st[1].tl = 1;
	st[1].tr = 1e9;
    for(int i=0;i<n;i++)
    {
        cin>>q>>a>>b;
        if(q==1)
        {
            c=query(1,a+c,b+c);
            cout<<c<<"\n";
        }
        else{
            update(1,a+c,b+c);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100