fork download
  1. /*
  2.   صل عل محمد
  3.   if (u == Abdel-Aziz Mostafa ) love u <3 ;
  4.   دايما احلم ربنا المنان
  5.  
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define N 300007
  11. //#define mod 1000
  12. #define int long long
  13. #define F first
  14. #define S second
  15.  
  16.  
  17. #define item pair< int , int >
  18.  
  19. struct node{
  20. // description
  21. bool op = 0 ;
  22. int oper =0 ;
  23. item val ;
  24.  
  25.  
  26. int lx , rx ; //when you crate the first root nd don't remeber to give it lx ,rx but other ndes take thier lft from up
  27.  
  28.  
  29. //intialize nd
  30. node (){
  31. //intialize
  32. oper = 0;
  33. val = {0,0} ;
  34. }
  35.  
  36. node * lft =NULL , *rght=NULL ; //create my two childs
  37. void extend() //طلعي تشيلدس
  38. {
  39.  
  40.  
  41. int md = (lx+rx)/2;
  42.  
  43. if (lft==NULL){
  44. lft = new node;
  45. lft ->lx =lx;
  46. lft->rx =md;
  47. }
  48.  
  49. if (rght==NULL){
  50. rght = new node;
  51. rght->lx= md;
  52. rght->rx = rx;
  53.  
  54. }
  55.  
  56. }
  57.  
  58. };
  59. node *root ;
  60. struct segtree{
  61.  
  62.  
  63.  
  64.  
  65. int sz =1, org ;
  66. segtree(int n){
  67. while(sz<n)sz*=2;
  68. root=new node;
  69. root->lx = 0 ;
  70. root->rx=sz;
  71. root->op = 0;
  72.  
  73. }
  74. int Neutral_elemnt = 0 ;
  75.  
  76. item merge(item m1 , item m2 ){
  77. return {max(m1.F,m2.F+m1.S ) , m1.S+m2.S};
  78.  
  79. }
  80.  
  81. int operation (int a , int b , bool op){
  82. if (!op)return b;
  83. return b;
  84. }
  85.  
  86. void apply(int& a ,int b , bool op){
  87. a=operation (a, b ,op);
  88. }
  89. void update(node *nd){
  90. if (nd->oper<0)
  91. nd->val.F=nd->oper;
  92. else
  93. nd->val.F =(nd->rx -nd->lx) *nd->oper;;
  94. nd->val.S = (nd->rx -nd->lx) *nd->oper;
  95. }
  96. void reset (node *nd){
  97.  
  98.  
  99. int lx = nd->lx , rx =nd->rx;
  100.  
  101. if (rx- lx==1){
  102. nd->val = make_pair(0, 0);
  103. if (nd->op)
  104. update(nd) ;
  105. }
  106. else {
  107. if (nd->lft==NULL and nd->rght==NULL){
  108. nd->val = {0 , 0} ;
  109. }
  110. else if (nd->rght==NULL){
  111. nd->val=nd->lft->val;
  112. }
  113. else if (nd->lft==NULL){
  114. nd->val=nd->rght->val;
  115. }
  116. else{
  117. nd->val= merge(nd->lft->val , nd->rght->val) ;
  118. }
  119. if (nd->op)
  120. update(nd) ;
  121. }
  122. }
  123. void propagate(node *nd){
  124. nd->extend();
  125. if (nd->rx-nd->lx==1 || !nd->op)
  126. return ;
  127.  
  128. apply(nd->lft->oper ,nd->oper , nd->lft->op) ;
  129. apply(nd->rght->oper ,nd->oper , nd->rght->op) ;
  130.  
  131.  
  132. nd->lft->op =nd->rght->op=1;
  133.  
  134. //clear op of node
  135. nd->op= 0 ;
  136. nd->val = {0,0} ;
  137. //////////////////////
  138.  
  139. reset(nd->lft); //عشان هي جالها تغيرات والمفروض انها مرتبطه بتفيراتها وال تحتيها
  140. reset(nd->rght); //same
  141. reset(nd); //same
  142. ////////////////////////////////////////////////////
  143.  
  144.  
  145. }
  146.  
  147. void change (int l , int r,int oper , node* nd){
  148.  
  149. // x lx rx val[x] oper[x] op[x] = nd || 2*x+1 >> nd->lft
  150.  
  151. if (nd->rx <=l || nd->lx >=r)
  152. return ;
  153.  
  154. propagate(nd);
  155.  
  156. if (nd->lx >=l and nd->rx<=r){
  157. apply( nd->oper, oper , nd->op );
  158. nd->op = 1;
  159. reset(nd) ;
  160. return ;
  161. }
  162.  
  163.  
  164. change( l, r, oper, nd->lft);
  165. change (l, r, oper , nd->rght);
  166. nd->val= merge(nd->lft->val , nd->rght->val) ;
  167. }
  168. void change (int l ,int r ,int oper){
  169. change(l,r , oper,root);
  170. }
  171.  
  172. int cnt_rails(int h , int en , node *nd){
  173.  
  174. nd->extend();
  175. propagate(nd);
  176.  
  177.  
  178. int lx =nd->lx, rx =nd->rx;
  179. if (rx-lx==1){
  180. return (((nd->val.F+en)<=h)?1:0);
  181. }
  182. int sh =en ;
  183.  
  184. if (nd->val.F+en<=h){
  185. return rx-lx;
  186. }
  187. sh+=nd->lft->val.S;
  188.  
  189. int md = (lx+rx)/2 ,len =(nd->rx-nd->lx)/2;
  190.  
  191. if (nd->lft->val.F+en<=h)
  192. return len +cnt_rails(h , sh , nd->rght);
  193.  
  194. return cnt_rails(h ,en ,nd->lft);
  195. }
  196. int cnt_rails(int h){
  197.  
  198. return cnt_rails(h,0 , root);
  199. }
  200.  
  201.  
  202.  
  203. };
  204. signed main() {
  205. ios_base::sync_with_stdio(0);
  206. cin.tie(0);
  207. cout.tie(0);
  208.  
  209.  
  210. int n ;
  211. cin>>n;
  212.  
  213. segtree sg(n);
  214.  
  215.  
  216.  
  217.  
  218. char q;
  219. cin>>q;
  220.  
  221. sg.change(n , n+1,1e15);
  222.  
  223. while(q!='E'){
  224.  
  225. if (q=='Q'){
  226. int h;
  227. cin>>h;
  228. cout<<sg.cnt_rails(h)<<"\n";
  229. }
  230. else {
  231. int l , r , d;
  232. cin>>l>>r>>d;
  233. int st= d ;
  234. l--;
  235. sg.change( l ,r , d);
  236. }
  237. cin>>q;
  238. }
  239.  
  240. }
Time limit exceeded #stdin #stdout 5s 1064140KB
stdin
Standard input is empty
stdout
Standard output is empty