Submission #989604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989604	2024-05-28T11:51:32 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	76 ms	200784 KB	Output is correct
2	Correct	78 ms	200784 KB	Output is correct
3	Correct	76 ms	200788 KB	Output is correct
4	Correct	83 ms	200788 KB	Output is correct
5	Correct	86 ms	200912 KB	Output is correct
6	Correct	84 ms	200968 KB	Output is correct
7	Correct	84 ms	201044 KB	Output is correct
8	Correct	150 ms	201812 KB	Output is correct
9	Correct	237 ms	202836 KB	Output is correct
10	Correct	246 ms	202832 KB	Output is correct
11	Correct	254 ms	203000 KB	Output is correct
12	Correct	249 ms	202768 KB	Output is correct
13	Correct	221 ms	203388 KB	Output is correct
14	Correct	211 ms	203348 KB	Output is correct
15	Execution timed out	2369 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-