Submission #984563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984563	2024-05-16T18:43:45 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	343 ms	186620 KB

apple

    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define MAXN 123456
     
    struct Segmentno{
        int levodete=-1;
        int desnodete=-1;
        int levagranica;
        int desnagranica;
        int suma=0;
        int lazy=0;
    };
     
    int m;
    Segmentno seg[64*MAXN];
    int cnt=2;
     
    void push(int node)
    {
        if (seg[node].lazy==0) return;
        seg[node].suma=seg[node].desnagranica-seg[node].levagranica+1;
        long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
        if (seg[node].levodete==-1)
        {
            seg[node].levodete=cnt;cnt++;
            seg[seg[node].levodete].levagranica=seg[node].levagranica;
            seg[seg[node].levodete].desnagranica=mid;
        }
        if (seg[node].desnodete==-1)
        {
            seg[node].desnodete=cnt;cnt++;
            seg[seg[node].desnodete].levagranica=mid+1;
            seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
        }
        seg[seg[node].levodete].lazy=1;
        seg[seg[node].desnodete].lazy=1;
        seg[node].lazy=0;
    }
     
    void update(int node,int l,int r)
    {
        push(node);
        if (l==seg[node].levagranica and r==seg[node].desnagranica) {seg[node].lazy=1;push(node);}
        else
        {
            int mid=(seg[node].levagranica+seg[node].desnagranica)/2;
            if (seg[node].levodete==-1)
            {
                seg[node].levodete=cnt;cnt++;
                seg[seg[node].levodete].levagranica=seg[node].levagranica;
                seg[seg[node].levodete].desnagranica=mid;
            }
            if (seg[node].desnodete==-1)
            {
                seg[node].desnodete=cnt;cnt++;
                seg[seg[node].desnodete].levagranica=mid+1;
                seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
            }
            if (l>mid) update(seg[node].desnodete,l,r);
            else if (r<=mid) update(seg[node].levodete,l,r);
            else
            {
                update(seg[node].levodete,l,mid);
                update(seg[node].desnodete,mid+1,r);
            }
            push(seg[node].levodete);
            push(seg[node].desnodete);
            seg[node].suma=seg[seg[node].levodete].suma+seg[seg[node].desnodete].suma;
        }
    }
     
    int query(int node,int l,int r)
    {
        push(node);
        if (l==seg[node].levagranica and r==seg[node].desnagranica) return seg[node].suma;
        int mid=(seg[node].levagranica+seg[node].desnagranica)/2;
        if (seg[node].levodete==-1)
        {
            seg[node].levodete=cnt;cnt++;
            seg[seg[node].levodete].levagranica=seg[node].levagranica;
            seg[seg[node].levodete].desnagranica=mid;
        }
        if (seg[node].desnodete==-1)
        {
            seg[node].desnodete=cnt;cnt++;
            seg[seg[node].desnodete].levagranica=mid+1;
            seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
        }
        if (l>mid) return query(seg[node].desnodete,l,r);
        else if (r<=mid) return query(seg[node].levodete,l,r);
        else return query(seg[node].levodete,l,mid)+query(seg[node].desnodete,mid+1,r);
    }
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>m;
        seg[1].levagranica=1;
        seg[1].desnagranica=1000000000;
        seg[1].suma=0,seg[1].lazy=0;
        int ans=0;
        for (int z=0;z<m;z++)
        {
            int t;cin>>t;
            if (t==1)
            {
                int x,y;cin>>x>>y;
                ans=query(1,x+ans,y+ans);
                cout<<ans<<endl;
            }
            else
            {
                int x,y;cin>>x>>y;
                update(1,x+ans,y+ans);
            }
        }
    }

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	185760 KB	Output is correct
2	Correct	59 ms	185936 KB	Output is correct
3	Correct	59 ms	185936 KB	Output is correct
4	Correct	70 ms	185780 KB	Output is correct
5	Correct	73 ms	185992 KB	Output is correct
6	Correct	73 ms	185968 KB	Output is correct
7	Correct	73 ms	185844 KB	Output is correct
8	Correct	163 ms	186028 KB	Output is correct
9	Correct	277 ms	186192 KB	Output is correct
10	Correct	281 ms	186196 KB	Output is correct
11	Correct	283 ms	186364 KB	Output is correct
12	Correct	301 ms	186320 KB	Output is correct
13	Correct	269 ms	186432 KB	Output is correct
14	Correct	261 ms	186452 KB	Output is correct
15	Correct	337 ms	186464 KB	Output is correct
16	Correct	326 ms	186448 KB	Output is correct
17	Correct	267 ms	186620 KB	Output is correct
18	Correct	260 ms	186328 KB	Output is correct
19	Correct	343 ms	186552 KB	Output is correct
20	Correct	334 ms	186452 KB	Output is correct