Submission #989592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989592	2024-05-28T11:38:17 Z	Aviansh	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

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
            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;
            }
            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
            push(ind,l,r);
            if(e<l||s>r)
                return 0;
            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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	200788 KB	Output is correct
2	Correct	77 ms	200788 KB	Output is correct
3	Correct	78 ms	200676 KB	Output is correct
4	Correct	91 ms	200768 KB	Output is correct
5	Correct	86 ms	201044 KB	Output is correct
6	Correct	85 ms	200784 KB	Output is correct
7	Correct	88 ms	200964 KB	Output is correct
8	Correct	158 ms	201872 KB	Output is correct
9	Correct	247 ms	202740 KB	Output is correct
10	Correct	242 ms	202836 KB	Output is correct
11	Correct	256 ms	202836 KB	Output is correct
12	Correct	254 ms	202832 KB	Output is correct
13	Correct	211 ms	203348 KB	Output is correct
14	Correct	208 ms	203348 KB	Output is correct
15	Execution timed out	2375 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-