Advertisement
IzhanVarsky

Untitled

Mar 24th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.89 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5.     private static int[][] tree;
  6.     // [0] - флаг актуальности
  7.     // [1] - цвет: 0 - белый, 1 - черный
  8.     // [2] - кол-во черных отрезков
  9.     // [3] - длина черных отрезков
  10.  
  11.     private static int SIZE = 1048576;
  12.  
  13.     private static void actionInRange(int v, int left, int right, int a, int b, int colour) {
  14.         if (a > b)
  15.             return;
  16.         if (a == left && right == b) {
  17.             setData(v, a, b, colour);
  18.             pushUp(v, a, b);
  19.         } else {
  20.             int mid = (left + right) / 2;
  21.             if (tree[v][0] == 1 && v * 2 + 2 < SIZE) {
  22.                 setData(v * 2 + 1, left, mid, tree[v][1]);
  23.                 setData(v * 2 + 2, mid + 1, right, tree[v][1]);
  24.                 tree[v][0] = 0;
  25.             }
  26.             actionInRange(v * 2 + 1, left, mid, a, Math.min(b, mid), colour);
  27.             actionInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b, colour);
  28.         }
  29.     }
  30.  
  31.     private static void setData(int v, int left, int right, int colour) {
  32.         tree[v][0] = 1;
  33.         tree[v][1] = tree[left][1] = tree[right][1] = colour;
  34.         if (colour == 1) {
  35.             tree[v][3] = right - left + 1;
  36.             tree[v][2] = 1;
  37.         } else {
  38.             tree[v][2] = tree[v][3] = 0;
  39.         }
  40.     }
  41.  
  42.     private static void pushUp(int v, int left, int right) {
  43.         if (v == 0)
  44.             return;
  45.         int nextLeft, nextRight;
  46.         int parent = (v - 1) / 2;
  47.         if (v % 2 == 1) { // левый сын
  48.             tree[parent][2] = tree[v][2] + tree[v + 1][2];
  49.             if (tree[right][1] == 1 && tree[right + 1][1] == 1) {
  50.                 tree[parent][2]--;
  51.             }
  52.             tree[parent][3] = tree[v][3] + tree[v + 1][3];
  53.             nextLeft = left;
  54.             nextRight = 2 * right - left + 1;
  55.         } else { // правый сын
  56.             tree[parent][2] = tree[v][2] + tree[v - 1][2];
  57.             if (tree[left - 1][1] == 1 && tree[left][1] == 1) {
  58.                 tree[parent][2]--;
  59.             }
  60.             tree[parent][3] = tree[v][3] + tree[v - 1][3];
  61.             nextLeft = 2 * left - right - 1;
  62.             nextRight = right;
  63.         }
  64.         pushUp(parent, nextLeft, nextRight);
  65.     }
  66.  
  67.     public static void main(String[] args) {
  68.         Scanner in = new Scanner(System.in);
  69.         tree = new int[SIZE][4];
  70.         int n = in.nextInt();
  71.         for (int i = 0; i < n; i++) {
  72.             String colour = in.next();
  73.             int left = in.nextInt();
  74.             int dist = in.nextInt();
  75.             int shift = 500000;
  76.             int colourCode = colour.equals("B") ? 1 : 0;
  77.             actionInRange(0, 0, SIZE / 2 - 1, left + shift, left + dist + shift - 1, colourCode);
  78.             System.out.println(tree[0][2] + " " + tree[0][3]);
  79.         }
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement