tetris

#include <iostream>

#define firstSon my_sons.first.first, my_sons.first.second
#define secondSon my_sons.second.first, my_sons.second.second

using namespace std;
#define MIXED -1

struct tree {
    int max_height;
    int act_height;
    tree *right_son;
    tree *left_son;

    tree() {
        max_height = 0;
        act_height = 0;
        left_son = nullptr;
        right_son = nullptr;
    }
}; // 1 cale biale, 0 cale czarne
tree *MainTree = new tree;

/*pair<pair<int, int>, pair<int, int>> sons(int l, int r) {
    int mid = (r + l) / 2;
    auto first = make_pair(l, mid);
    auto second = make_pair(mid + 1, r);
    return make_pair(first, second);
}*/

int D; //szerokosc platformy
int N; //number of blocks

void build_tree(tree *tli, int l, int r) {
    if (l >= r) {
        return;
    }
    tli->right_son = new tree;
    tli->left_son = new tree;
    int mid = (r + l) / 2;

    build_tree(tli->left_son, l, mid);
    build_tree(tli->right_son, mid + 1, r);
}

void cumming_on_sons (tree *t) {
    if (t -> left_son) {
        t -> left_son -> act_height = max(t -> act_height,
                                          t -> left_son -> act_height);
    }
    if (t -> right_son) {
        t -> right_son -> act_height = max(t -> act_height,
                                           t -> right_son -> act_height);
    }
}

int max_height(tree *t, int lb, int rb, int l, int r) {
    if (!t) {
        return 0;
    }
    if (l == lb && r == rb) {
        return t -> max_height;
    }
    int mid = (rb + lb) / 2;
    if (r <= mid) {
        return max_height(t->left_son, lb, mid, l, r);
    }
    else if (l >= mid + 1) {
        return max_height(t->right_son, mid + 1, rb, l, r);
    }
    else {
    int one_slice = max_height(t->left_son, lb, mid, l, mid);
    int second_slice = max_height(t->right_son, mid + 1, rb, mid + 1, r);
    return max(one_slice, second_slice);
    }
}

void put_block(tree *t, int lb, int rb, int l, int r, int new_height) {
    if (!t) {
        return;
    }
    t -> max_height = max(t->max_height, new_height);
    if (l == lb && r == rb) {
        t -> max_height = new_height;
        t -> act_height = new_height;
        return;
    }
    if (t -> act_height != MIXED) {
        cumming_on_sons(t);
    }
    t -> act_height = MIXED;
    int mid = (rb + lb) / 2;
    if (r <= mid) {
        put_block(t->left_son, lb, mid, l, r, new_height);
    }
    else if (mid + 1 <= l) {
        put_block(t->right_son, mid + 1, rb, l, r, new_height);
    }
    else {
        put_block(t->left_son, lb, mid, l, mid, new_height);
        put_block(t->right_son, mid + 1, rb, mid + 1, r, new_height);
    }
    if (t->left_son && t->right_son && t->left_son->act_height == t->right_son->act_height) {
        t->act_height = t->left_son->act_height;
    }
}

int main() {
    cin >> D >> N;
    build_tree(MainTree, 1, D);
    for (int i = 0; i < N; ++i) {
        int x, l;
        cin >> l >> x;
        int a = x;
        int b = x + l;
        int new_height = max_height(MainTree, 1, D, a, b) + 1;
        put_block(MainTree, 1, D, a, b, new_height);
        cout << MainTree->max_height << endl;
    }
    cout << MainTree->max_height;
    return 0;
}