Advertisement
Guest User

Untitled

a guest
May 22nd, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. //#include "optimization.h"
  4.  
  5. using std::cin;
  6. using std::cout;
  7. using std::pair;
  8. using std::make_pair;
  9. using std::string;
  10.  
  11. template<typename T>
  12. class seg_tree_down {
  13.   public:
  14.     enum color {WHITE, BLACK};
  15.  
  16.     seg_tree_down(size_t size) {
  17.         size_t nN;
  18.         for (nN = 1; nN <= size; nN *= 2);
  19.         if (nN < size)
  20.             nN *= 2;
  21.  
  22.         N_ = nN;
  23.         delta_ = nN - size;
  24.         //cout << "d = " << delta_ << "\n" << "N = " << N_ << "\n";
  25.  
  26.         sum_ = new T[nN * 2];
  27.         cl_ = new color[nN * 2];
  28.         cr_ = new color[nN * 2];
  29.         nsegs_ = new T[nN * 2];
  30.  
  31.         for (size_t i = 0; i < nN * 2; i++) {
  32.             sum_[i] = 0;
  33.             cl_[i] = WHITE;
  34.             cr_[i] = WHITE;
  35.             nsegs_[i] = 0;
  36.         }
  37.     }
  38.  
  39.     void paint(color clr, size_t left, size_t right) {
  40.         left += (N_ + delta_);
  41.         right += (N_ + delta_);
  42.  
  43.         //cout << "left = " << left << "\nright = " << right << "\n";
  44.  
  45.         rpaint(clr, 1, 1, 2 * N_, left, right);
  46.     }
  47.  
  48.     T nuber_of_segs() {
  49.         return nsegs_[1];
  50.     }
  51.  
  52.     T len() {
  53.         return sum_[1];
  54.     }
  55.   private:
  56.     void rpaint(color clr, size_t v, size_t vl, size_t vr, size_t l, size_t r, string tab = "") {
  57.         //cout << tab << "[" << vl << ", " << vr << ")\n";
  58.         if (l >= vr || r <= vl)
  59.             return;
  60.         if (l <= vl && vr <= r) {
  61.  
  62.             if (clr == BLACK) {
  63.                 sum_[v] = vr - vl;
  64.                 nsegs_[v] = 1;
  65.             } else {
  66.                 sum_[v] = 0;
  67.                 nsegs_[v] = 0;
  68.             }
  69.  
  70.             cl_[v] = clr;
  71.             cr_[v] = clr;
  72.  
  73.             //cout << tab << "_LEFT is " << ((cl_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
  74.             //cout << tab << "_RIGHT is " << ((cr_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
  75.             //cout << tab << "_LENGHT = " << sum_[v] << "\n";
  76.             //cout << tab << "_BS = " << nsegs_[v] << '\n';
  77.  
  78.             return;
  79.         }
  80.  
  81.         rpaint(clr, v * 2, vl, vl + (vr - vl) / 2, l, r, tab + "  ");
  82.         rpaint(clr, v * 2 + 1, vl + (vr - vl) / 2, vr, l, r, tab + "  ");
  83.  
  84.         cl_[v] = cl_[v * 2];
  85.         cr_[v] = cr_[v * 2 + 1];
  86.         nsegs_[v] = nsegs_[v * 2] + nsegs_[v * 2 + 1] - (cr_[v * 2] == BLACK && cl_[v * 2 + 1] == BLACK);
  87.         sum_[v] = sum_[v * 2] + sum_[v * 2 + 1];
  88.  
  89.         // cout << tab << "LEFT is " << ((cl_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
  90.         // cout << tab << "RIGHT is " << ((cr_[v] == WHITE)? "WHITE" : "BLACK") << '\n';
  91.         // cout << tab << "LENGHT = " << sum_[v] << "\n";
  92.         // cout << tab << "BS = " << nsegs_[v] << '\n';
  93.     }
  94.  
  95.  
  96.   private:
  97.     T *sum_;
  98.     T *nsegs_;
  99.  
  100.     color *cl_;
  101.     color *cr_;
  102.  
  103.     size_t N_;
  104.     size_t delta_;
  105. };
  106.  
  107. int main() {
  108.     int N;
  109.     cin >> N;
  110.     seg_tree_down<size_t> line(10000);
  111.  
  112.     char ch;
  113.     int left, lenght;
  114.     for (int i = 0; i < N; i++) {
  115.         cin >> ch >> left >> lenght;
  116.         left++;
  117.  
  118.         if (ch == 'W') {
  119.             line.paint(seg_tree_down<size_t>::WHITE, left, left + lenght);
  120.             cout << line.nuber_of_segs() << ' ' << line.len() << '\n';
  121.         } else if (ch == 'B') {
  122.             line.paint(seg_tree_down<size_t>::BLACK, left, left + lenght);
  123.             cout << line.nuber_of_segs() << ' ' << line.len() << '\n';
  124.         } else  {
  125.             cout << "KEK\n";
  126.         }
  127.     }
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement