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 from[200010/B+1], to[200010/B+1];
int val[200010/B*B+B];

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 block(int l, int r, int x){
  //assert(l%B == 0 && r%B == 0);
  l /= B; 
  r /= B;
  while(l < r){
    if(to[l] != -1){
      to[l] = (to[l] == x-1) ? x : -2;
    } else {
      from[l] = x-1;
      to[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(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);
  }

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