Submission #989603

#	Time	Username	Problem	Language	Result	Execution time	Memory
989603		Aviansh	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	84 ms	200852 KiB

apple

#include <bits/stdc++.h>

using namespace std;

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

template<class node> class lazySegTree{
    private:
        long long n;
        node *st;
        long long *laz;
        long long cn=1;
    public:
        lazySegTree(long long siz, long long maxnode){
            st = new node[maxnode];
            laz = new long long[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(long long ind){
            if(st[ind].lc==-1||st[ind].rc==-1){
                st[ind].lc=cn++;
                st[ind].rc=cn++;
            }
        }
        void push(long long ind, long long l, long long 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(long long l, long long r, long long s, long long e, long long ind, long long val){
            //l-r is real range, s-e is to be updated
            if(l>e||r<s){
                return;
            }
            push(ind,l,r);
            if(s<=l&&r<=e){
                st[ind].val=val*(r-l+1);
                laz[st[ind].lc]=val;
                laz[st[ind].rc]=val;
                return;
            }
            long long 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(long long l, long long r, long long val){
            realUpdate(0,n,l,r,0,val);
        }
        long long realQuery(int l, int r, int s, int e, int ind){
            //l-r is real range, s-e is query
            if(e<l||s>r)
                return 0;
            push(ind,l,r);
            if(s<=l&&r<=e){
                return st[ind].val;
            }
            long long mid = (l+r)/2;
            return realQuery(l,mid,s,e,st[ind].lc)+realQuery(mid+1,r,s,e,st[ind].rc);
        }
        long long query(long long l, long long r){
            return realQuery(0,n,l,r,0);
        }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> m;
    long long c=0;
    lazySegTree<node> lst((long long)1e9,(long long)(64*1e5));
    while(m--){
        long long 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