제출 #1203008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203008		Aviansh	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	258 ms	196628 KiB

apple

#include <bits/stdc++.h>

using namespace std;

//range set range sum query

struct node{
    int lef, rig;
    long long val;
};

struct lazySparseSegTree{
    node *st;
    int *laz;
    int n;
    int cr = 0;
    lazySparseSegTree(int nodes, int siz){
        //default is 0
        node def = {-1,-1,0};
        st = new node[nodes];
        laz = new int[nodes];
        fill(st,st+nodes,def);
        fill(laz,laz+nodes,-1);
        n=siz-1;
    }
    void makeKids(int ind, int l, int r){
        if(l==r){
            return;
        }
        if(st[ind].lef==-1){
            st[ind].lef=++cr;
        }
        if(st[ind].rig==-1){
            st[ind].rig=++cr;
        }
    }
    void pushDown(int ind, int l, int r){
        makeKids(ind,l,r);
        if(laz[ind]==-1)
            return;
        st[ind].val=1LL*(laz[ind])*(r-l+1);
        laz[st[ind].lef]=laz[ind];
        laz[st[ind].rig]=laz[ind];
        laz[ind]=-1;
    }

    void rupdate(int l, int r, int s, int e, int ind, int val){
        pushDown(ind,l,r);
        if(r<s||l>e)
            return;
        if(s<=l&&r<=e){
            laz[ind]=val;
            pushDown(ind,l,r);
            return;
        }
        int mid = (l+r)/2;
        rupdate(l,mid,s,e,st[ind].lef,val);
        rupdate(mid+1,r,s,e,st[ind].rig,val);
        st[ind].val=st[st[ind].lef].val+st[st[ind].rig].val;
    }

    void update(int l, int r, int val){
        rupdate(0,n,l,r,0,val);
    }

    long long rquery(int l, int r, int s, int e, int ind){
        if(r<s||l>e){
            return 0;
        }
        pushDown(ind,l,r);
        if(s<=l&&r<=e){
            return st[ind].val;
        }
        int mid = (l+r)/2;
        return rquery(l,mid,s,e,st[ind].lef)+rquery(mid+1,r,s,e,st[ind].rig);
    }

    long long query(int l, int r){
        return rquery(0,n,l,r,0);
    }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> q;
    lazySparseSegTree lsst(1e7,1e9+5);
    int c = 0;
    while(q--){
        int d,l,r;
        cin >> d >> l >> r;
        l+=c;
        r+=c;
        if(d==1){
            c=lsst.query(l,r);
            cout << c << "\n";
        }
        else{
            lsst.update(l,r,1);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100