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;
typedef long long ll;


using T = tuple<int, int, int>;// l,r,k
using P = pair<int, int>;// t, k
vector<P> in[200000];
vector<P> out[200000];
int cnt[200010];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream ifs("in");
	std::cin.rdbuf(ifs.rdbuf());
#endif

	int N, K, Q;
	cin >> N >> K >> Q;
	for(int i = 0; i < Q; i++){
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		in[l].push_back({ i, k });
		out[r].push_back({ i, k });
	}
	int ans = 0, NG = 0;
	set<P> s;
	map<int, int> cm;
	cm[0] = K;
	for(int i = 0; i < N; i++){
		for(auto x : in[i]){
			s.insert(x);
			auto it = s.find(x);
			if(it != s.begin()){
				auto pre = prev(it);
				if(pre->second >= it->second) NG++;
				auto nxt = next(it);
				if(nxt != s.end()){
					if(pre->second >= nxt->second) NG--;
				}
			}
			{
				auto nxt = next(it);
				if(nxt != s.end()){
					if(it->second >= nxt->second) NG++;
				}
			}

			cm[cnt[x.second]]--;
			cnt[x.second]++;
			cm[cnt[x.second]]++;
		}

		if(NG == 0 && cm[1] == K && s.size() == K){
			ans++;
		}

		for(auto x : out[i]){
			auto it = s.find(x);
			if(it != s.begin()){
				auto pre = prev(it);
				if(pre->second >= it->second) NG--;
				auto nxt = next(it);
				if(nxt != s.end()){
					if(pre->second >= nxt->second) NG++;
				}
			}
			{
				auto nxt = next(it);
				if(nxt != s.end()){
					if(it->second >= nxt->second) NG--;
				}
			}

			s.erase(x);
			cm[cnt[x.second]]--;
			cnt[x.second]--;
			cm[cnt[x.second]]++;
		}
	}
	cout << ans << endl;
}