Submission #989612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989612	2024-05-28T12:05:24 Z	Aviansh	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	301 ms	201572 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	200780 KB	Output is correct
2	Correct	80 ms	200800 KB	Output is correct
3	Correct	82 ms	200788 KB	Output is correct
4	Correct	105 ms	200800 KB	Output is correct
5	Correct	90 ms	200788 KB	Output is correct
6	Correct	89 ms	200784 KB	Output is correct
7	Correct	94 ms	200784 KB	Output is correct
8	Correct	149 ms	201036 KB	Output is correct
9	Correct	214 ms	201044 KB	Output is correct
10	Correct	225 ms	200992 KB	Output is correct
11	Correct	231 ms	201012 KB	Output is correct
12	Correct	221 ms	201124 KB	Output is correct
13	Correct	214 ms	201572 KB	Output is correct
14	Correct	203 ms	201332 KB	Output is correct
15	Correct	267 ms	201296 KB	Output is correct
16	Correct	257 ms	201296 KB	Output is correct
17	Correct	217 ms	201296 KB	Output is correct
18	Correct	254 ms	201304 KB	Output is correct
19	Correct	301 ms	201244 KB	Output is correct
20	Correct	286 ms	201188 KB	Output is correct