답안 #989596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989596	2024-05-28T11:42:54 Z	Aviansh	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	200784 KB	Output is correct
2	Correct	75 ms	200768 KB	Output is correct
3	Correct	75 ms	200784 KB	Output is correct
4	Correct	83 ms	200788 KB	Output is correct
5	Correct	86 ms	200784 KB	Output is correct
6	Correct	86 ms	200792 KB	Output is correct
7	Correct	84 ms	200840 KB	Output is correct
8	Correct	148 ms	200884 KB	Output is correct
9	Correct	242 ms	201044 KB	Output is correct
10	Correct	241 ms	201040 KB	Output is correct
11	Correct	248 ms	201044 KB	Output is correct
12	Correct	256 ms	201204 KB	Output is correct
13	Correct	255 ms	201240 KB	Output is correct
14	Correct	215 ms	201296 KB	Output is correct
15	Execution timed out	2361 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-