Advertisement
IzhanVarsky

Untitled

Mar 24th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. const int SIZE = 1048576 * 2 - 1;
  7. int tree[SIZE][6];
  8.  
  9. void actionInRange(int v, int left, int right, int a, int b, int colour);
  10.  
  11. void setData(int v, int colour);
  12.  
  13. void setLeftAndRightForNodes(int v, int left, int right);
  14.  
  15. void pushUp(int v);
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(NULL);
  20.     cout.tie(NULL);
  21.     int n;
  22.     cin >> n;
  23.     setLeftAndRightForNodes(0, SIZE / 2, SIZE - 1);
  24.     for (int i = 0; i < n; i++) {
  25.         string colour;
  26.         cin >> colour;
  27.         int left, dist;
  28.         cin >> left >> dist;
  29.         int shift = 500000;
  30.         int colourCode = colour == "B" ? 1 : 0;
  31.         actionInRange(0, 0, SIZE / 2, left + shift, left + dist + shift - 1, colourCode);
  32.         cout << tree[0][2] << " " << tree[0][3] << endl;
  33.     }
  34.     return 0;
  35. }
  36.  
  37. void actionInRange(int v, int left, int right, int a, int b, int colour) {
  38.     if (left > b || right < a)
  39.         return;
  40.     if (a <= left && right <= b) {
  41.         setData(v, colour);
  42.         pushUp(v);
  43.     } else {
  44.         if (tree[v][0] == 1 && v * 2 + 2 < SIZE) {
  45.             setData(v * 2 + 1, tree[v][1]);
  46.             setData(v * 2 + 2, tree[v][1]);
  47.             tree[v][0] = 0;
  48.         }
  49.         int mid = (left + right) / 2;
  50.         actionInRange(v * 2 + 1, left, mid, a, b, colour);
  51.         actionInRange(v * 2 + 2, mid + 1, right, a, b, colour);
  52.     }
  53. }
  54.  
  55. void setData(int v, int colour) {
  56.     int left = tree[v][4];
  57.     int right = tree[v][5];
  58.     tree[v][0] = 1;
  59.     tree[v][1] = tree[left][1] = tree[right][1] = colour;
  60.     if (colour == 1) {
  61.         tree[v][3] = right - left + 1;
  62.         tree[v][2] = 1;
  63.     } else {
  64.         tree[v][2] = tree[v][3] = 0;
  65.     }
  66. }
  67.  
  68. void pushUp(int v) {
  69.     if (v == 0)
  70.         return;
  71.     int parent = (v - 1) / 2;
  72.     int left = tree[v][4];
  73.     int right = tree[v][5];
  74.     if (v % 2 == 1) { // левый сын
  75.         tree[parent][2] = tree[v][2] + tree[v + 1][2];
  76.         if (tree[right][1] == 1 && tree[right + 1][1] == 1) {
  77.             tree[parent][2]--;
  78.         }
  79.         tree[parent][3] = tree[v][3] + tree[v + 1][3];
  80.     } else { // правый сын
  81.         tree[parent][2] = tree[v][2] + tree[v - 1][2];
  82.         if (tree[left - 1][1] == 1 && tree[left][1] == 1) {
  83.             tree[parent][2]--;
  84.         }
  85.         tree[parent][3] = tree[v][3] + tree[v - 1][3];
  86.     }
  87.     pushUp(parent);
  88. }
  89.  
  90. void setLeftAndRightForNodes(int v, int left, int right) {
  91.     tree[v][4] = left;
  92.     tree[v][5] = right;
  93.     int mid = (left + right) / 2;
  94.     if (v * 2 + 2 < SIZE) {
  95.         setLeftAndRightForNodes(v * 2 + 1, left, mid);
  96.         setLeftAndRightForNodes(v * 2 + 2, mid + 1, right);
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement