답안 #989608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989608	2024-05-28T12:01:27 Z	Aviansh	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	241 ms	205904 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct node{
    int lc=-1;
    int rc=-1;
    int val=0;
};

template<class node> class lazySegTree{
    private:
        int n;
        node *st;
        int *laz;
        int cn=1;
    public:
        lazySegTree(int siz, int maxnode){
            st = new node[maxnode];
            laz = new int[maxnode];
            node def;
            def.lc=-1;
            def.rc=-1;
            def.val=0;
            fill(st,st+maxnode,def);
            n=siz;
            fill(laz,laz+maxnode,0);
            makeKids(0);
        }
        void makeKids(int ind){
            if(st[ind].lc==-1||st[ind].rc==-1){
                st[ind].lc=cn++;
                st[ind].rc=cn++;
            }
        }
        void push(int ind, int l, int r){
            if(l!=r)
                makeKids(ind);
            if(laz[ind]!=0){
                st[ind].val=laz[ind]*(r-l+1);
                if(l!=r){
                    laz[st[ind].lc]=laz[ind];
                    laz[st[ind].rc]=laz[ind];
                }
                laz[ind]=0;
            }
        }

        void realUpdate(int l, int r, int s, int e, int ind, int val){
            //l-r is real range, s-e is to be updated
            push(ind,l,r);
            if(l>e||r<s){
                return;
            }
            if(s<=l&&r<=e){
                st[ind].val=val*(r-l+1);
                laz[st[ind].lc]=val;
                laz[st[ind].rc]=val;
                return;
            }
            int mid = (l+r)/2;
            realUpdate(l,mid,s,e,st[ind].lc,val);
            realUpdate(mid+1,r,s,e,st[ind].rc,val);
            st[ind].val=st[st[ind].lc].val+st[st[ind].rc].val;
        }

        void update(int l, int r, int val){
            realUpdate(0,n,l,r,0,val);
        }
        int realQuery(int l, int r, int s, int e, int ind){
            //l-r is real range, s-e is query
            push(ind,l,r);
            if(e<l||s>r)
                return 0;
            if(s<=l&&r<=e){
                return st[ind].val;
            }
            int mid = (l+r)/2;
            return realQuery(l,mid,s,e,st[ind].lc)+realQuery(mid+1,r,s,e,st[ind].rc);
        }
        int query(int l, int r){
            return realQuery(0,n,l,r,0);
        }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> m;
    int c=0;
    lazySegTree<node> lst((int)1e9,(int)(64*1e5));
    while(m--){
        int d,x,y;
        cin >> d >> x >> y;
        if(d==2){
            lst.update(x+c,y+c,1);
        }
        else{
            c = lst.query(x+c,y+c);
            cout << c << "\n";
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	100440 KB	Output is correct
2	Correct	43 ms	100536 KB	Output is correct
3	Correct	44 ms	100436 KB	Output is correct
4	Correct	49 ms	100692 KB	Output is correct
5	Correct	50 ms	100688 KB	Output is correct
6	Correct	50 ms	100688 KB	Output is correct
7	Correct	52 ms	100688 KB	Output is correct
8	Correct	107 ms	101656 KB	Output is correct
9	Correct	191 ms	102740 KB	Output is correct
10	Correct	182 ms	102712 KB	Output is correct
11	Correct	192 ms	102736 KB	Output is correct
12	Correct	185 ms	102704 KB	Output is correct
13	Correct	165 ms	103040 KB	Output is correct
14	Correct	166 ms	102992 KB	Output is correct
15	Runtime error	241 ms	205904 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-