Submission #646153

#	Time	Username	Problem	Language	Result	Execution time	Memory
646153		QuinnG	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	212 KiB

apple

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;

struct SegTree{

    ll sum=0, lazySum=0;
    SegTree *left, *right;
    int L,R;

    SegTree(int l, int r){
        // delete this to make implicit
        // if(l!=r){
        //     int mid = (l+r)/2;
        //     left = new SegTree(l,mid);
        //     right = new SegTree(mid+1,r);
        // }
        L = l;
        R = r;
        left = nullptr;
        right = nullptr;
    }

    ll getValue(){
        return lazySum*(R-L+1) + sum;
    }

    void check(){
        if(left==nullptr){
            int mid = (L+R)/2;
            left = new SegTree(L,mid);
            right = new SegTree(mid+1,R);
        }
    }

    void prop(){
        check();
        left->lazySum += lazySum;
        right->lazySum += lazySum;
        lazySum = 0;
        sum = left->getValue() + right->getValue();
    }

    // range sum
    ll query(int l, int r){
        // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<sum<<" "<<lazySum<<" "<<getValue()<<endl;
        if(l<=L && r>=R) return getValue();
        if(l>R || r<L) return 0;
        prop();
        return left->query(l,r) + right->query(l,r);
    }
    
    // range add
    void update(int l, int r, int x){
        if(l<=L && r>=R) lazySum += x;
        else if(l>R || r<L) return;
        else {
            prop();
            left->update(l,r,x);
            right->update(l,r,x);
            sum = left->getValue()+right->getValue();
        }
    }

    // range set
    void set(int l, int r, int x){
        if(l<=L && r>=R){
            sum = 0;
            lazySum = x;
            int mid = (L+R)/2;
            left = new SegTree(L,mid);
            right = new SegTree(mid+1,R);
        }else if(l>R || r<L){
            return;
        }else{
            prop();
            left->set(l,r,x);
            right->set(l,r,x);
            sum = left->getValue()+right->getValue();
        }
    }

};

int main(){

    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int m;cin>>m;
    SegTree tree(-2e9,2e9);
    int c = 0;
    for(int i=0;i<m;i++){
        int type,l,r;cin>>type>>l>>r;
        // cout<<type<<endl;
        if(type==1){
            cout<<tree.query(l+c,r+c)<<endl;
            c += tree.query(l,r);
        }else{
            tree.set(l+c,r+c,1);
        }
    }

}

• Subtask 1: 0 / 100