// ayy // ' lamo #include #include using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; //CARE typedef complex pt; #define fi first #define se second #define pb push_back const ld eps=1e-8; const int inf=1e9+99; const ll linf=1e18+99; const int P=1e9+7; template struct custom_node_update { public: typedef int metadata_type; int Qh(CIt it,int y) { if(it==node_end()) return 0; int ltot=(it.get_l_child()==node_end() ? 0 : it.get_l_child().get_metadata()); int mtot=(*it)->se-(*it)->fi; if(y>=(*it)->se) return ltot+mtot+Qh(it.get_r_child(),y); if(y>=(*it)->fi) return ltot+y-(*it)->fi; return Qh(it.get_l_child(),y); } int Q(int y) { return Qh(node_begin(),y); } inline void operator()(It it,CIt end_it) { It LC=it.get_l_child(), RC=it.get_r_child(); auto &md=it.get_metadata(); const_cast(md)=(*it)->se-(*it)->fi; if(LC!=end_it) const_cast(md) += LC.get_metadata(); if(RC!=end_it) const_cast(md) += RC.get_metadata(); } virtual CIt node_begin() const = 0; virtual CIt node_end() const = 0; virtual ~custom_node_update() {} }; tree< pair, null_type, less >, rb_tree_tag, custom_node_update > ints; int32_t main() { int n; scanf("%d",&n); vector > vv; for(int i=0;ise>P.se) { int L=it->fi; int R=it->se; ints.erase({L,R}); ints.insert({L,P.se}); ints.insert({P.se,R}); continue; } if(it->se-it->fi > used) { int L=it->fi; int R=it->se; ints.erase({L,R}); ints.insert({L,R-used}); used=0; continue; } used-=it->se-it->fi; ints.erase(it); } } printf("%d\n",Z); }