제출 #646166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646166		QuinnG	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	520 ms	205972 KiB

apple

#include <bits/stdc++.h>

using namespace std;

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

struct SegTree{
 
    int sum=0, lazySum=0, lazySet=0;
    bool needSet = false;
    SegTree *left, *right;
    int L,R;
 
    SegTree(int l, int r){
        // 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;
    }

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

    int getValue(){
        if(needSet){
            return (lazySum+lazySet)*(R-L+1);
        }else{
            return lazySum*(R-L+1) + sum;
        }
    }
 
    void prop(){
        check();
        if(needSet){
            left->lazySet = lazySet;
            left->needSet = true;
            left->lazySum = 0;
            right->lazySet = lazySet;
            right->needSet = true;
            right->lazySum = 0;
        }
        left->lazySum += lazySum;
        right->lazySum += lazySum;
        lazySum = 0;
        lazySet = 0;
        needSet = false;
        sum = left->getValue() + right->getValue();
    }
 
    // range sum
    int query(int l, int r){
        // cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<sum<<" "<<lazySum<<" "<<lazySet<<" "<<needSet<<" "<<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){
            // cout<<"SET "<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<sum<<" "<<lazySum<<" "<<lazySet<<" "<<needSet<<" "<<getValue()<<endl;
            lazySet = x;
            lazySum = 0;
            needSet = true;
            // cout<<"SET "<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<sum<<" "<<lazySum<<" "<<lazySet<<" "<<needSet<<" "<<getValue()<<endl;
        }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(0,1e9);
    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+c,r+c);
        }else{
            tree.set(l+c,r+c,1);
        }
    }

}

• Subtask 1: 100 / 100