Advertisement
shamiul93

!

May 5th, 2017
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll                                      long long
  3. #define fi                                      freopen("in.txt", "r", stdin)
  4. #define fo                                      freopen("out.txt", "w", stdout)
  5. #define m0(a) memset(a , 0 , sizeof(a))
  6. #define m1(a) memset(a , -1 , sizeof(a))
  7.  
  8. #define mx 100009
  9. using namespace std;
  10. ll N, i, j ;
  11.  
  12. struct node
  13. {
  14.     ll sum   ;
  15.     ll prop ;
  16. };
  17.  
  18. typedef struct node node ;
  19.  
  20. node seg[mx*5] ;
  21.  
  22. void pushUp(ll sp)
  23. {
  24.     seg[sp].sum = seg[2*sp+1].sum + seg[2*sp+2].sum ;
  25. }
  26.  
  27.  
  28. void pushdown(ll lo, ll hi, ll sp)
  29. {
  30.     if(seg[sp].prop == -1)
  31.     {
  32.         return ;
  33.     }
  34.  
  35.     ll mid ;
  36.     mid = (lo+hi) / 2 ;
  37.  
  38.     ll l, r ;
  39.  
  40.     l = mid - lo + 1 ;
  41.     r = hi - (mid + 1) + 1 ;
  42.  
  43.  
  44.     seg[2*sp+1].prop = seg[sp].prop ;
  45.     seg[2*sp+1].sum = seg[sp].prop * l ; // what is the point of update it ..... you have already put it in your lazy
  46.     seg[2*sp+2].prop = seg[sp].prop ;
  47.     seg[2*sp+2].sum = seg[sp].prop * r ; // same problem
  48.  
  49.     seg[sp].prop = -1 ;
  50.     return ;
  51. }
  52.  
  53. // what is the point of returning a node????
  54. node update(ll lo, ll hi, ll sp, ll x)
  55. {
  56.     //you have to push down first cause what if there is a update but you return
  57.  
  58.     if(lo > j || hi < i )
  59.     {
  60.         return node();
  61.     }
  62.     if(lo >= i && hi <= j)
  63.     {
  64.         ll n ;
  65.         n = (hi - lo + 1) ;
  66.  
  67.         seg[sp].prop = x ;
  68.         seg[sp].sum = n * x ;
  69.         //what about lazy tree you don't update it
  70.         //you just update your current node
  71.         //also you dont clear your current lazy
  72.         return seg[sp] ;
  73.     }
  74.  
  75.     pushdown(lo, hi, sp) ; // this potion going in top
  76.  
  77.     ll mid ;
  78.     mid = (lo+hi) / 2 ;
  79.  
  80.  
  81.     update(lo, mid, 2*sp+1, x) ;
  82.     update(mid+1, hi, 2*sp+2, x) ;
  83.  
  84.     seg[sp].sum = seg[2*sp+1].sum + seg[2*sp+2].sum ;
  85.  
  86.  
  87.     pushUp(sp) ;
  88.     return seg[sp] ;
  89. }
  90.  
  91.  
  92. ll query(ll lo, ll hi, ll sp)
  93. {
  94.     //you have to push down first cause what if there is a update but you return
  95.  
  96.     if(lo > j || hi < i)
  97.     {
  98.         return 0 ;
  99.     }
  100.     if(lo >= i && hi <= j)
  101.     {
  102.         ll n ;
  103.         n = hi - lo + 1 ;
  104.         return seg[sp].sum ;
  105.     }
  106.  
  107.     pushdown(lo, hi, sp) ; // same problem
  108.  
  109.     ll mid ;
  110.     mid = (lo+hi) / 2 ;
  111.  
  112.     ll r = 0  ;
  113.     r += query(lo, mid, 2*sp+1) ;
  114.     r += query(mid+1, hi, 2*sp+2) ;
  115.  
  116.     return r ;
  117. }
  118.  
  119. //i think its ok ... but you can double check it
  120. ll gcd(ll a, ll b)
  121. {
  122.     if(a < b)
  123.     {
  124.         swap(a,b) ;
  125.     }
  126.     ll r, d ;
  127.     while(b != 0)
  128.     {
  129.         r = a % b ;
  130.         a = b ;
  131.         b = r ;
  132.     }
  133.     return a ;
  134. }
  135.  
  136. int main()
  137. {
  138. //    fi ;
  139. //    fo ;
  140.     ll T ;
  141.     scanf("%lld",&T);
  142.     ll t = 0 ;
  143.     ll q, c ;
  144.     while(T--)
  145.     {
  146.         for(ll k = 0 ; k < mx*5 ; k++)
  147.         {
  148.             seg[k].sum = 0  ;
  149.             seg[k].prop = -1 ;
  150.         }
  151.  
  152.         t++ ;
  153.         scanf("%lld %lld",&N, &q) ;
  154. //        cout << q << endl ;
  155.         printf("Case %lld:\n",t) ;
  156.         while(q--)
  157.         {
  158.             scanf("%lld",&c) ;
  159.             if(c==2)
  160.             {
  161.                 scanf("%lld %lld",&i, &j) ;
  162.                 ll ans, n ;
  163.                 n = j - i + 1 ;
  164.                 ans = query(0, N-1, 0) ;
  165. //                cout << ans << endl ;
  166.                 if(ans % n == 0)
  167.                 {
  168.                     printf("%lld\n",ans / n) ;
  169.                 }
  170.                 else
  171.                 {
  172.                     ll g = gcd(ans, n) ;
  173.                     ll nom, denom ;
  174.                     nom = ans /  g ;
  175.                     denom = n / g ;
  176.                     printf("%lld/%lld\n",nom, denom) ;
  177.                 }
  178. //                if(q!=0)
  179. //                {
  180. //                    printf("\n") ;
  181. //                }
  182.             }
  183.             else if(c==1)
  184.             {
  185.                 ll v ;
  186.                 scanf("%lld %lld %lld", &i, &j, &v) ;
  187.                 update(0, N-1, 0, v) ;
  188.             }
  189.         }
  190.     }
  191.  
  192.     return 0 ;
  193. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement