CPP_Classrooms

#include <algorithm>
#include <cstdio>
#include <utility>

#define RANK(x) ((1 << (31 - __builtin_clz(x))) - 1)

using interval = std::pair<int, int>;

struct node {
    int value;
    int numvalid;
    int min;
    int count;
};

int update(node* tree, int start, int end, int s, int f) {
    int root = start + RANK(end - start);
    if (tree[root].min >= s) return 0;

    int lvl = 0;
    int parents[20];
    int p_end[20];

    int best = -1;
    int bestlvl = -1;

    for (;;) {
        auto [val, num, min, count] = tree[root];
        int oldend = end;
        if (val < s) {
            if (count) {
                best = root;
                bestlvl = lvl - 1;
                start = root + 1;
            } else {
                int right_start = root + 1;
                int left_end = root;

                if (right_start >= end) {
                    end = left_end;
                } else {
                    int right_root = right_start + RANK(end - right_start);
                    if (tree[right_root].numvalid < 1) {
                        end = left_end;
                    } else {
                        if (tree[right_root].min >= s) {
                            end = left_end;
                        } else {
                           start = right_start;
                        }
                    }
                }
            }
        } else {
            end = root;
        }
        if (start >= end) break;
        int oldroot = root;
        root = start + RANK(end - start);
        if (tree[root].numvalid < 1 || tree[root].min >= s) break;
        parents[lvl] = oldroot;
        p_end[lvl] = oldend;
        lvl++;
    }

    auto &[val, numvalid, min, count] = tree[best];
    count--;
    numvalid--;
    for(int i = bestlvl; i >= 0; i--) tree[parents[i]].numvalid--;

    if (count == 0) {
        int newmin = min;
        if (min == val) {
            if (numvalid) {
                newmin = tree[root].min;
            } else {
                if (bestlvl == -1) newmin = f;
                else {
                    for(int l = bestlvl;;l--) {
                        int n = parents[l];
                        node *p = &tree[n];
                        if (p->numvalid) {
                            if (p->count > 0) newmin = p->value;
                            else {
                                int p_r_start = n+1;
                                int p_r_end = p_end[l];
                                int r = p_r_start + RANK(p_r_end-p_r_start);
                                newmin = tree[r].min;
                            }
                            break;
                        }
                    }
                }
            }
        }
        for(int i = bestlvl; i >= 0; i--) {
            node *p = &tree[parents[i]];
            if (p->min == min) p->min = newmin;
        }
        min = newmin;
    }
    return 1;
}

int main() {
    int n, k;
    scanf("%d %d\n", &n, &k);
    interval* intervals = new interval[n];

    for(int i = 0; i < n; i++) {
        scanf("%d %d\n", &intervals[i].first, &intervals[i].second);
    }
    std::sort(intervals, intervals+n, [](interval a, interval b) {
        return a.second < b.second;
    });

    int start = 0, end = 1;

    node* tree = new node[1 + n];
    tree[0] = {0,k,0,k};

    int count = 0;
    for(int i = 0; i < n; i++) {
        auto [s, f] = intervals[i];
        int success = update(tree, start, end, s, f);
        if (success) {
            bool eq = false;
            if (tree[end-1].value == f) { tree[end-1].count++; eq = true; }
            else tree[end++] = {f, 0, f, 1};
            int numvalid = tree[end-1].numvalid+1;
            int min = f;
            int _start = 0, _end = end;
            int _root = _start + RANK(_end-_start);
            for(; tree[_root].value != f;) {
                tree[_root].numvalid++;
                _start = _root + 1;
                _root = _start + RANK(_end-_start);
            }
            if (((end-1) & 1) == 1 && !eq) {
                _end = _root;
                if (_start < _end) {
                    _root = _start + RANK(_end-_start);
                    min = tree[_root].numvalid > 0 ? tree[_root].min : f;
                    numvalid = tree[_root].numvalid + 1;
                }
                tree[end-1].min = min;
            }
            tree[end-1].numvalid = numvalid;
            count += 1;
        }
    }
    printf("%d\n", count);
    return 0;
}