Submission #989601

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989601	2024-05-28T11:44:40 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	75 ms	200784 KB	Output is correct
2	Correct	73 ms	200664 KB	Output is correct
3	Correct	76 ms	200784 KB	Output is correct
4	Correct	83 ms	200784 KB	Output is correct
5	Correct	88 ms	200952 KB	Output is correct
6	Correct	85 ms	200784 KB	Output is correct
7	Correct	85 ms	200788 KB	Output is correct
8	Correct	148 ms	200808 KB	Output is correct
9	Correct	238 ms	201136 KB	Output is correct
10	Correct	233 ms	201044 KB	Output is correct
11	Correct	243 ms	201040 KB	Output is correct
12	Correct	244 ms	201044 KB	Output is correct
13	Correct	210 ms	201296 KB	Output is correct
14	Correct	203 ms	201300 KB	Output is correct
15	Execution timed out	2421 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-