Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- private static int[][] tree;
- // [0] - флаг актуальности
- // [1] - цвет: 0 - белый, 1 - черный
- // [2] - кол-во черных отрезков
- // [3] - длина черных отрезков
- private static int SIZE = 1048576;
- private static void actionInRange(int v, int left, int right, int a, int b, int colour) {
- if (a > b)
- return;
- if (a == left && right == b) {
- setData(v, a, b, colour);
- pushUp(v, a, b);
- } else {
- int mid = (left + right) / 2;
- if (tree[v][0] == 1 && v * 2 + 2 < SIZE) {
- setData(v * 2 + 1, left, mid, tree[v][1]);
- setData(v * 2 + 2, mid + 1, right, tree[v][1]);
- tree[v][0] = 0;
- }
- actionInRange(v * 2 + 1, left, mid, a, Math.min(b, mid), colour);
- actionInRange(v * 2 + 2, mid + 1, right, Math.max(a, mid + 1), b, colour);
- }
- }
- private static void setData(int v, int left, int right, int colour) {
- tree[v][0] = 1;
- tree[v][1] = tree[left][1] = tree[right][1] = colour;
- if (colour == 1) {
- tree[v][3] = right - left + 1;
- tree[v][2] = 1;
- } else {
- tree[v][2] = tree[v][3] = 0;
- }
- }
- private static void pushUp(int v, int left, int right) {
- if (v == 0)
- return;
- int nextLeft, nextRight;
- int parent = (v - 1) / 2;
- if (v % 2 == 1) { // левый сын
- tree[parent][2] = tree[v][2] + tree[v + 1][2];
- if (tree[right][1] == 1 && tree[right + 1][1] == 1) {
- tree[parent][2]--;
- }
- tree[parent][3] = tree[v][3] + tree[v + 1][3];
- nextLeft = left;
- nextRight = 2 * right - left + 1;
- } else { // правый сын
- tree[parent][2] = tree[v][2] + tree[v - 1][2];
- if (tree[left - 1][1] == 1 && tree[left][1] == 1) {
- tree[parent][2]--;
- }
- tree[parent][3] = tree[v][3] + tree[v - 1][3];
- nextLeft = 2 * left - right - 1;
- nextRight = right;
- }
- pushUp(parent, nextLeft, nextRight);
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- tree = new int[SIZE][4];
- int n = in.nextInt();
- for (int i = 0; i < n; i++) {
- String colour = in.next();
- int left = in.nextInt();
- int dist = in.nextInt();
- int shift = 500000;
- int colourCode = colour.equals("B") ? 1 : 0;
- actionInRange(0, 0, SIZE / 2 - 1, left + shift, left + dist + shift - 1, colourCode);
- System.out.println(tree[0][2] + " " + tree[0][3]);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement