Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	int start,end;
};

int N = 1;
Info* donut;

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value_start,int new_value_end,int node_id,int node_left,int node_right){
	if(update_right < node_left || update_left > node_right){
		return;
	}
	else if(update_left <= node_left && update_right >= node_right){

		if(donut[node_id].start == 0 && donut[node_id].end == 0){
			donut[node_id].start = new_value_start;
			donut[node_id].end = new_value_end;
		}else{
			if(donut[node_id].end+1 == new_value_start){
				donut[node_id].end = new_value_end;
			}else{

				donut[node_id].start = BIG_NUM;
				donut[node_id].end = BIG_NUM;
			}
		}

	}else{

		if(donut[node_id].start != 0){
			update(node_left,node_right,donut[node_id].start,donut[node_id].end,2*node_id+1,node_left,(node_left+node_right)/2);
			update(node_left,node_right,donut[node_id].start,donut[node_id].end,2*node_id+2,(node_left+node_right)/2+1,node_right);
		}

		donut[node_id].start = 0;
		donut[node_id].end = 0;

		update(update_left,update_right,new_value_start,new_value_end,2*node_id+1,node_left,(node_left+node_right)/2);
		update(update_left,update_right,new_value_start,new_value_end,2*node_id+2,(node_left+node_right)/2+1,node_right);
	}
}

void merge_range(int node_id){

	int loc = node_id+N-1;
	int left = donut[loc].start,right = donut[loc].end;

	int parent_id = (loc-1)/2;

	while(true){
		if(donut[parent_id].start == 0 && donut[parent_id].end == 0){
			//Do nothing
		}else{
			if(left == 0 && right == 0){
				left = donut[parent_id].start;
				right = donut[parent_id].end;
			}else{
				if(right+1 == donut[parent_id].start){
					right = donut[parent_id].end;
				}else{
					left = BIG_NUM;
					right = BIG_NUM;
					break;
				}
			}
		}
		if(parent_id == 0)break;
		parent_id = (parent_id-1)/2;
	};

	donut[loc].start = left,donut[loc].end = right;
}

int main(){

	int first_N,K,T;
	scanf("%d %d",&first_N,&K);
	scanf("%d",&T);

	init(first_N);
	donut = new Info[2*N-1];

	for(int i = 0; i <= 2*N-2; i++){
		donut[i].start = 0;
		donut[i].end = 0;
	}

	int left,right,task_id;
	for(int loop = 0; loop < T; loop++){
		scanf("%d %d %d",&left,&right,&task_id);
		left--;
		right--;

		update(left,right,task_id,task_id,0,0,N-1);
	}

	for(int i = 0; i < first_N; i++)merge_range(i);

	int ans = 0;
	for(int i = 0; i < first_N; i++){
		if(donut[N-1+i].start == 1 && donut[N-1+i].end == K)ans++;
	}

	printf("%d\n",ans);

	return 0;
}