Untitled

mail@pastecode.io avatar
unknown
c_cpp
24 days ago
2.3 kB
3
Indexable
Never
class MyCalendarThree {
public:
    struct node{
        node * L ,*R;
        int val , tag;
        node(int v):val(v),L(NULL),R(NULL),tag(0){};
    };
    void push(node * nd){
        if(!nd->L) nd->L = new node(0);
        if(!nd->R) nd->R = new node(0);
        nd->L->tag += nd->tag;
        nd->R->tag += nd->tag;
        nd->val += nd->tag;
        nd->tag = 0;
        return;
    }
    node * modify(int ql,int qr,int cl,int cr,int v,node* nd){
        if(!nd) nd = new node(0);
        if(cr == cl || (ql == cl && qr == cr)){
            nd->tag += v;
            if(cr != cl){
                push(nd);
            }else{
                nd->val += nd->tag;
                nd->tag = 0;
            }
            return nd;
        }
        push(nd);
        int mid = (cl + cr)/2;
        if(ql > mid){
            nd->R = modify(ql,qr,mid+1,cr,v,nd->R);
        }else if(qr <= mid){
            nd->L = modify(ql,qr,cl,mid,v,nd->L);
        }else{
            nd->R = modify(mid+1,qr,mid+1,cr,v,nd->R);
            nd->L = modify(ql,mid,cl,mid,v,nd->L);
        }
        if(nd->R) nd->val = max(nd->val , nd->R->val);
        if(nd->L) nd->val = max(nd->val , nd->L->val);
        return nd;
    }
    int query(int ql,int qr,int cl,int cr,node* nd){
        if(!nd)return 0;
        if(cr != cl) push(nd);
        else {
            nd->val += nd->tag;
            nd->tag = 0;
        }
        if(cr == cl || (ql == cl && qr == cr)){
            return nd->val;
        }
        int mid = (cl + cr)/2;
        if(ql > mid){
            return query(ql,qr,mid+1,cr,nd->R);
        }else if(qr <= mid){
            return query(ql,qr,cl,mid,nd->L);
        }else{
            int rres = query(mid+1,qr,mid+1,cr,nd->R);
            int lres = query(ql,mid,cl,mid,nd->L);
            return max(lres, rres);
        }
    }
    node * root;
    int max_ed = 1e9+8;
    MyCalendarThree() {
        root= NULL;
    }
    
    int book(int startTime, int endTime) {
        root = modify(startTime , endTime-1 , 0, max_ed ,1, root);
        return root->val;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */
Leave a Comment