Submission #1082628

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082628	2024-08-31T20:31:14 Z	LeonidCuk	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	384 ms	188752 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	185940 KB	Output is correct
2	Correct	68 ms	185940 KB	Output is correct
3	Correct	69 ms	185940 KB	Output is correct
4	Correct	88 ms	185984 KB	Output is correct
5	Correct	80 ms	186016 KB	Output is correct
6	Correct	88 ms	185936 KB	Output is correct
7	Correct	83 ms	186096 KB	Output is correct
8	Correct	186 ms	186792 KB	Output is correct
9	Correct	295 ms	187992 KB	Output is correct
10	Correct	306 ms	187992 KB	Output is correct
11	Correct	312 ms	187984 KB	Output is correct
12	Correct	309 ms	188060 KB	Output is correct
13	Correct	302 ms	188496 KB	Output is correct
14	Correct	293 ms	188496 KB	Output is correct
15	Correct	357 ms	188752 KB	Output is correct
16	Correct	358 ms	188500 KB	Output is correct
17	Correct	301 ms	188500 KB	Output is correct
18	Correct	303 ms	188500 KB	Output is correct
19	Correct	384 ms	188496 KB	Output is correct
20	Correct	354 ms	188500 KB	Output is correct