Submission #984559

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984559	2024-05-16T18:42:52 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	384 ms	262144 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[60*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	45 ms	141140 KB	Output is correct
2	Correct	43 ms	141148 KB	Output is correct
3	Correct	43 ms	141148 KB	Output is correct
4	Correct	54 ms	141360 KB	Output is correct
5	Correct	57 ms	141348 KB	Output is correct
6	Correct	58 ms	141144 KB	Output is correct
7	Correct	61 ms	141392 KB	Output is correct
8	Correct	140 ms	141424 KB	Output is correct
9	Correct	263 ms	141648 KB	Output is correct
10	Correct	288 ms	141648 KB	Output is correct
11	Correct	272 ms	141728 KB	Output is correct
12	Correct	280 ms	141904 KB	Output is correct
13	Correct	272 ms	141652 KB	Output is correct
14	Correct	250 ms	141668 KB	Output is correct
15	Runtime error	384 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-