Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- using namespace std;
- const int SIZE = 1048576 * 2 - 1;
- int tree[SIZE][6];
- void actionInRange(int v, int left, int right, int a, int b, int colour);
- void setData(int v, int colour);
- void setLeftAndRightForNodes(int v, int left, int right);
- void pushUp(int v);
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- int n;
- cin >> n;
- setLeftAndRightForNodes(0, SIZE / 2, SIZE - 1);
- for (int i = 0; i < n; i++) {
- string colour;
- cin >> colour;
- int left, dist;
- cin >> left >> dist;
- int shift = 500000;
- int colourCode = colour == "B" ? 1 : 0;
- actionInRange(0, 0, SIZE / 2, left + shift, left + dist + shift - 1, colourCode);
- cout << tree[0][2] << " " << tree[0][3] << endl;
- }
- return 0;
- }
- void actionInRange(int v, int left, int right, int a, int b, int colour) {
- if (left > b || right < a)
- return;
- if (a <= left && right <= b) {
- setData(v, colour);
- pushUp(v);
- } else {
- if (tree[v][0] == 1 && v * 2 + 2 < SIZE) {
- setData(v * 2 + 1, tree[v][1]);
- setData(v * 2 + 2, tree[v][1]);
- tree[v][0] = 0;
- }
- int mid = (left + right) / 2;
- actionInRange(v * 2 + 1, left, mid, a, b, colour);
- actionInRange(v * 2 + 2, mid + 1, right, a, b, colour);
- }
- }
- void setData(int v, int colour) {
- int left = tree[v][4];
- int right = tree[v][5];
- 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;
- }
- }
- void pushUp(int v) {
- if (v == 0)
- return;
- int parent = (v - 1) / 2;
- int left = tree[v][4];
- int right = tree[v][5];
- 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];
- } 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];
- }
- pushUp(parent);
- }
- void setLeftAndRightForNodes(int v, int left, int right) {
- tree[v][4] = left;
- tree[v][5] = right;
- int mid = (left + right) / 2;
- if (v * 2 + 2 < SIZE) {
- setLeftAndRightForNodes(v * 2 + 1, left, mid);
- setLeftAndRightForNodes(v * 2 + 2, mid + 1, right);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement