Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

const int BUCKET_SIZE = 512;
const int MAXN = 200010;

int N, K, T;
int node[MAXN], invalid_node[MAXN];
int bucket[BUCKET_SIZE], cons[BUCKET_SIZE], invalid_bucket[BUCKET_SIZE];

void lazy_update(int i) {
  int sl = i*BUCKET_SIZE, sr = sl + BUCKET_SIZE;
  // 区間更新値があれば適用
  if(cons[i] > 0) {
    // i: index for bucket
    // k: index for node
    for(int k=sl; k<sr; k++) {
      if(bucket[i] - cons[i] != node[k]) {
	invalid_node[k] = true;
      }
      else {
	node[k] = bucket[i];
      }
    }
    cons[i] = 0;
  }
}

void update(int l, int r, int x) {
  for(int i=0; i<BUCKET_SIZE; i++) {
    int sl = i*BUCKET_SIZE, sr = sl + BUCKET_SIZE;
    if(r <= sl or sr <= l) continue;
    if(l <= sl and sr <= r) {
      if(cons[i] > 0) {
	// 区間更新されるような値が以前に存在
	if(x - bucket[i] != 1) {
	  invalid_bucket[i] = true;
	}
	else {
	  bucket[i] = x;
	  cons[i]++;
	}
      }
      else {
	// 区間更新値がはじめてきた
	bucket[i] = x;
	cons[i] = 1;
      }
    }
    else {
      lazy_update(i);
      for(int k=max(l,sl); k<min(r,sr); k++) {
	if(x - node[k] != 1) {
	  invalid_node[k] = true;
	}
	else {
	  node[k] = x;
	}
      }
    }
  }
}

bool is_valid_node(int node_id) {
  int bucket_id = node_id / BUCKET_SIZE;
  lazy_update(bucket_id);
  if(invalid_bucket[bucket_id]) return false;
  if(invalid_node[node_id]) return false;
  return node[node_id] == K;
}

int main() {
  cin >> N >> K >> T;
  for(int i=0; i<T; i++) {
    int l, r, x; cin >> l >> r >> x; l--;
    update(l, r, x);
  }
  int ans = 0;
  for(int i=0; i<N; i++) {
    ans += is_valid_node(i);
  }
  cout << ans << endl;
  return 0;
}