답안 #989610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989610	2024-05-28T12:02:58 Z	Aviansh	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	272 ms	201404 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)(128*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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	200788 KB	Output is correct
2	Correct	86 ms	200784 KB	Output is correct
3	Correct	82 ms	200788 KB	Output is correct
4	Correct	95 ms	200784 KB	Output is correct
5	Correct	90 ms	200692 KB	Output is correct
6	Correct	92 ms	200788 KB	Output is correct
7	Correct	97 ms	200784 KB	Output is correct
8	Correct	144 ms	200788 KB	Output is correct
9	Correct	218 ms	201216 KB	Output is correct
10	Correct	223 ms	201044 KB	Output is correct
11	Correct	236 ms	201320 KB	Output is correct
12	Correct	232 ms	201104 KB	Output is correct
13	Correct	198 ms	201404 KB	Output is correct
14	Correct	210 ms	201296 KB	Output is correct
15	Correct	264 ms	201300 KB	Output is correct
16	Correct	259 ms	201300 KB	Output is correct
17	Correct	212 ms	201296 KB	Output is correct
18	Correct	211 ms	201296 KB	Output is correct
19	Correct	272 ms	201296 KB	Output is correct
20	Correct	262 ms	201100 KB	Output is correct