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;

int N,K,T;

const int B = 100;
int from[200010/B+1], to[200010/B+1];
int val[200010/B*B+B];

void show(){
  return;
  for(int i = 0; i < N; ++i){
    cout << val[i] << ' ';
  }
  cout << endl;
  for(int i = 0; i < N/B; ++i){
    cout << from[i] << ' ';
  }
  cout << endl;
  for(int i = 0; i < N/B; ++i){
    cout << to[i] << ' ';
  }
  cout << endl;
}

void sync(int b){
  if(from[b] == -1) return;
  for(int i = b*B; i < (b+1)*B; ++i){
    if(val[i] == from[b]){
      val[i] = to[b];
    } else {
      val[i] = -2;
    }
  }
  from[b] = -1;
  to[b] = -1;
}

void naive(int l, int r, int x){
  for(int i = l; i < r; ++i){
    val[i] = (val[i] == x-1) ? x : -2;
  }
}

void exec(int l, int r, int x){
  if(l/B == r/B){
    sync(l/B);
    naive(l,r,x);
  } else {
    if(l%B){
      sync(l/B);
      naive(l, l-l%B+B, x);
      l = l-l%B+B;
    }
    if(r%B){
      sync(r/B);
      naive(r-r%B, r, x);
      r = r-r%B;
    }
    while(l+B <= r){
      // cout << "u" << l << endl;
      if(to[l/B] != -1){
	to[l/B] = (to[l/B] == x-1) ? x : -2;
      } else {
	from[l/B] = x-1;
	to[l/B] = x;
      }
      l += B;
    }
  }

  show();
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  cin >> N >> K;
  cin >> T;

  memset(from, -1, sizeof from);
  memset(to, -1, sizeof to);

  while(N%B) ++N;

  for(int it = 0; it < T; ++it){
    int l,r,x;
    cin >> l >> r >> x;
    --l;
    exec(l,r,x);
  }

  for(int i = 0; i < N/B; ++i){
    sync(i);
  }
  show();

  cout << count(val, val+N, K) << endl;
}