Problem: Example

Input

3 2
3
1 2 1
2 3 2
3 3 1


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <set>

void solve() {
    int n, k, t;
    std::cin >> n >> k >> t;

    std::vector<std::vector<int>> ls(n), rs(n);
    std::vector<int> xs(t + 2);
    xs[0] = 0;
    for (int i = 1; i <= t; ++i) {
        int l, r;
        std::cin >> l >> r >> xs[i];
        ls[--l].push_back(i);
        rs[--r].push_back(i);
    }
    xs[t + 1] = k + 1;

    std::set<int> ts{0, t + 1};
    int out = 1, ans = 0;
    for (int i = 0; i < n; ++i) {
        for (auto x : ls[i]) {
            auto it = ts.lower_bound(x);
            int nxt = *it;
            --it;
            int prev = *it;

            if (xs[nxt] - xs[prev] != 1) --out;
            if (xs[x] - xs[prev] != 1) ++out;
            if (xs[nxt] - xs[x] != 1) ++out;
            ts.insert(x);
        }

        if (out == 0) ++ans;

        for (auto x : rs[i]) {
            ts.erase(x);
            auto it = ts.lower_bound(x);
            int nxt = *it;
            --it;
            int prev = *it;

            if (xs[x] - xs[prev] != 1) --out;
            if (xs[nxt] - xs[x] != 1) --out;
            if (xs[nxt] - xs[prev] != 1) ++out;
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}