Untitled
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