Advertisement
K_Y_M_bl_C

KALE\V/1CH

Jan 11th, 2017
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. struct tree
  2. {
  3.     int val, cnt, set, lb, rb;
  4.     tree()
  5.     {
  6.         val = 0;
  7.         cnt = 0;
  8.         lb = 0;
  9.         rb = 0;
  10.         set = -1;
  11.     };
  12. };
  13.  
  14. const int Q = (int)4e6 + 7;
  15.  
  16. tree t[Q];
  17. int l, r, col;
  18.  
  19. void push(int v, int tl, int tr)
  20. {
  21.     if (t[v].set != -1)
  22.     {
  23.         t[v].val = t[v].set * (tr - tl + 1);
  24.         t[v].lb = t[v].set;
  25.         t[v].rb = t[v].set;
  26.         t[v].cnt = t[v].set;
  27.         if (tl != tr)
  28.         {
  29.             t[2 * v + 1].set = t[v].set;
  30.             t[2 * v + 2].set = t[v].set;
  31.         }
  32.         t[v].set = -1;
  33.     }
  34. }
  35.  
  36. void update(int v, int tl, int tr)
  37. {
  38.     push(v, tl, tr);
  39.     if (l <= tl && tr <= r)
  40.     {
  41.         t[v].set = col;
  42.         push(v, tl, tr);
  43.         return;
  44.     }
  45.     int tm = tl + tr >> 1;
  46.     if (!(tl > r || tm < l))
  47.         update(2 * v + 1, tl, tm);
  48.     else
  49.         push(2 * v + 1, tl, tm);
  50.     if (!((tm + 1) > r || tr < l))
  51.         update(2 * v + 2, tm + 1, tr);
  52.     else
  53.         push(2 * v + 2, tm + 1, tr);
  54.     t[v].val = t[2 * v + 1].val + t[2 * v + 2].val;
  55.     t[v].cnt = t[2 * v + 1].cnt + t[2 * v + 2].cnt;
  56.     if (t[2 * v + 1].rb == t[2 * v + 2].lb && t[2 * v + 2].lb == 1)
  57.         --t[v].cnt;
  58.     t[v].lb = t[2 * v + 1].lb;
  59.     t[v].rb = t[2 * v + 2].rb;
  60. }
  61.  
  62. int n;
  63.  
  64. int solve()
  65. {
  66.     scanf("%d", &n);
  67.     forn(i, n)
  68.     {
  69.         char cl;
  70.         int len;
  71.         scanf(" %c %d %d", &cl, &l, &len);
  72.         r = l + len - 1;
  73.         col = (cl == 'B');
  74.         update(0, -500000, 500000);
  75.         printf("%d %d\n", t[0].cnt, t[0].val);
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement