Submission #984557

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984557	2024-05-16T18:41:50 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	294 ms	191312 KB

apple

    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define MAXN 100010
     
    struct Segmentno{
        int levodete=-1;
        int desnodete=-1;
        int levagranica;
        int desnagranica;
        int suma=0;
        int lazy=0;
    };
     
    int m;
    Segmentno seg[40*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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	94288 KB	Output is correct
2	Correct	24 ms	94292 KB	Output is correct
3	Correct	24 ms	94296 KB	Output is correct
4	Correct	35 ms	94292 KB	Output is correct
5	Correct	39 ms	94288 KB	Output is correct
6	Correct	38 ms	94300 KB	Output is correct
7	Correct	40 ms	94340 KB	Output is correct
8	Correct	124 ms	94436 KB	Output is correct
9	Correct	260 ms	94844 KB	Output is correct
10	Correct	247 ms	94548 KB	Output is correct
11	Correct	258 ms	94652 KB	Output is correct
12	Correct	251 ms	94672 KB	Output is correct
13	Runtime error	294 ms	191312 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-