fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mhb2PB
language:
C++ (gcc 8.3)
created:
62 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!