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 = 512;
int bfr[200010/B+1], aft[200010/B+1];
int val[200010/B*B+B];

void sync(int b){
  if(bfr[b] == -1) return;
  for(int i = b*B; i < (b+1)*B; ++i){
    val[i] = (val[i] == bfr[b]) ? aft[b] : -2;
  }
  bfr[b] = -1;
  aft[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 block(int l, int r, int x){
  l /= B; 
  r /= B;
  while(l < r){
    if(aft[l] != -1){
      aft[l] = (aft[l] == x-1) ? x : -2;
    } else {
      bfr[l] = x-1;
      aft[l] = x;
    }
    ++l;
  }  
}

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;
    }
    block(l,r,x);
  }
}

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

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

  memset(bfr, -1, sizeof bfr);
  memset(aft, -1, sizeof aft);

  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);
  }

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