답안 #984557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984557	2024-05-16T18:41:50 Z	ivaziva	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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	-