Submission #984562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984562	2024-05-16T18:43:20 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	398 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[70*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	50 ms	164712 KB	Output is correct
2	Correct	56 ms	164744 KB	Output is correct
3	Correct	56 ms	164740 KB	Output is correct
4	Correct	65 ms	164720 KB	Output is correct
5	Correct	66 ms	164692 KB	Output is correct
6	Correct	68 ms	164856 KB	Output is correct
7	Correct	68 ms	164856 KB	Output is correct
8	Correct	174 ms	164924 KB	Output is correct
9	Correct	301 ms	165216 KB	Output is correct
10	Correct	297 ms	165164 KB	Output is correct
11	Correct	303 ms	165100 KB	Output is correct
12	Correct	290 ms	165304 KB	Output is correct
13	Correct	275 ms	165204 KB	Output is correct
14	Correct	263 ms	165280 KB	Output is correct
15	Runtime error	398 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-