Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

using pii = pair<int, int>;
#define fst first
#define snd second

const pii fail = pii(-1, -1);


inline pii exec(pii cur, pii add) {
	if (cur == fail or add == fail) return fail;
	if (cur.snd == 0) return add;
	if (cur.snd != add.fst) return fail;
	return pii(cur.fst, add.snd);
}

const int sz = 1 << 18;
pii data[2 * sz], lazy[2 * sz];

inline void lazy_eval(int k) {
	if (lazy[k].snd == 0) return;

	for (int nk = 2 * k + 1; nk <= 2 * k + 2; ++nk) {
		data[nk] = exec(data[nk], lazy[k]);
		lazy[nk] = exec(lazy[nk], lazy[k]);
	}

	lazy[k].snd = 0;
}

void query(int a, int b, int k, pii add, int l, int r) {
	if (b <= l or r <= a ) return;

	if (a <= l and r <= b) {
		data[k] = exec(data[k], add);
		lazy[k] = exec(lazy[k], add);
		return ;
	}

	lazy_eval(k);

	const int m = (l + r) / 2;
	query(a, b, 2 * k + 1, add, l, m);
	query(a, b, 2 * k + 2, add, m, r);
}


int main(void) {
	int n, k, t;
	cin >> n >> k >> t;

	rep(i, 2 * sz) {
		data[i] = pii(0, 1);
		lazy[i] = pii(0, 0);
	}

	rep(loop, t) {
		int l, r, x;
		cin >> l >> r >> x, l--;
		query(l, r, 0, pii(x, x + 1), 0, sz);
	}

	rep(i, sz - 1) lazy_eval(i);

	int ans = 0;
	rep(i, n){
		//cerr << data[sz - 1 + i].fst << " " << data[sz - 1 + i].snd << endl;
		if (data[sz - 1 + i].fst == 0 and data[sz - 1 + i].snd == k + 1) ans++;
	}
	cout << ans << endl;

}