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>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef pair< int, int > pii;

class Decoration {
private:
	int n;
	vector< pii > deco, job;
	
	int toLeft(int k) { return (k << 1) + 1; }
	int toRight(int k) { return (k << 1) + 2; }
	int center(int l, int r) { return (l + r) >> 1; }
	
	pii mixDeco(pii fp, pii sp) {
		if (fp.first == 0) return sp;
		if (sp.first == 0) return fp;
		if (fp.first < 0 || sp.first < 0) return pii(-1,-1);
		if (fp.second + 1 == sp.first) return pii(fp.first, sp.second);
		return pii(-1, -1);
	}
	
	void lazyEval(int k, int l, int r) {
		deco[k] = mixDeco(deco[k], job[k]);
		if (k < n-1) {
			job[toLeft(k)] = mixDeco(job[toLeft(k)], job[k]);
			job[toRight(k)] = mixDeco(job[toRight(k)], job[k]);
		}
		job[k] = pii(0,0);
	}
	
	void addDeco(int a, int b, int x, int k, int l, int r) {
		lazyEval(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			job[k] = pii(x, x);
			lazyEval(k, l, r);
			return;
		}
		addDeco(a, b, x, toLeft(k), l, center(l, r));
		addDeco(a, b, x, toRight(k), center(l, r), r);
	}
	
	pii getDeco(int a, int k, int l, int r) {
		lazyEval(k, l, r);
		if (l == a && r == a+1) return deco[k];
		int c = center(l, r);
		if (a < c) return getDeco(a, toLeft(k), l, c);
		else return getDeco(a, toRight(k), c, r);
	}
	
public:
	Decoration(int __n) {
		for (n=1; n<__n; n<<=1);
		deco.assign(2*n, pii(0,0));
		job.assign(2*n, pii(0,0));
	}
	
	void addDeco(int a, int b, int x) { addDeco(a, b, x, 0, 0, n); }
	pii getDeco(int a) { return getDeco(a, 0, 0, n); }
};

int main() {
	int N, K;
	cin >> N >> K;
	
	Decoration deco(N);
	
	int T;
	cin >> T;
	for_(i,0,T) {
		int l, r, x;
		cin >> l >> r >> x;
		deco.addDeco(l-1, r, x);
	}
	
	int ans = 0;
	for_(i,0,N) {
		pii p = deco.getDeco(i);
		if (p.first == 1 && p.second == K) ++ans;
	}
	cout << ans << endl;
}