POI Task Cards

#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>

using namespace std;

const int INF = 1e9;

struct Segment {
    int l[2], r[2]; // l are start values, r are corresponding min end values
    Segment () {}
    Segment (int x, int y) {
        l[0] = r[0] = x;
        l[1] = r[1] = y;
    }
    Segment (int l0, int l1, int r0, int r1) {
        l[0] = l0;
        l[1] = l1;
        r[0] = r0;
        r[1] = r1;
    }
};
struct Node {
    Segment s;
    Node * left, * right;
};
Segment combine(Segment a, Segment b) {
    Segment s(a.l[0], a.l[1], INF, INF);
    if (a.r[0] <= b.l[0]) s.r[0] = b.r[0];
    else if (a.r[0] <= b.l[1]) s.r[0] = b.r[1];
    if (a.r[1] <= b.l[0]) s.r[1] = b.r[0];
    else if (a.r[1] <= b.l[1]) s.r[1] = b.r[1];
    return s;
}
Segment combine(Node * &a, Node * &b) {
    assert(a || b);
    if (!a) return b->s;
    if (!b) return a->s;
    return combine(a->s, b->s);
}
void update(Node * &base, int l, int r, int i, int x, int y) {
    if (l+1 == r) {
        base->s = {x, y};
        return;
    }
    int m = (l + r) / 2;
    if (i < m) {
        if (!base->left) base->left = new Node();
        update(base->left, l, m, i, x, y);
    } else {
        if (!base->right) base->right = new Node();
        update(base->right, m, r, i, x, y);
    }
    base->s = combine(base->left, base->right);
}
bool queryPossible(Node * &root) {
    return root->s.r[0] != INF;
}

int main() {
    int n; cin >> n;
    Node * root = new Node();
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        if (x[i] > y[i]) swap(x[i], y[i]);
        update(root, 0, n, i, x[i], y[i]);
    }
    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        --a, --b;
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        update(root, 0, n, a, x[a], y[a]);
        update(root, 0, n, b, x[b], y[b]);
        cout << (queryPossible(root) ? "TAK" : "NIE") << '\n';
    }
    return 0;
}