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;
#define BS 500
#define MAX 214514
int up[500],fr[500],to[500],ou[500];
int dn[MAX];
void eval(int p){
  if(!up[p]) return;
  for(int j=BS*p;j<BS*(p+1);j++){
    if(dn[j]==fr[p]) dn[j]=to[p];
    else dn[j]=-1;
  }
  up[p]=0;
}
signed main(){
  int n,k,t;
  cin>>n>>k>>t;
  memset(up,0,sizeof(up));
  memset(fr,0,sizeof(fr));
  memset(to,0,sizeof(to));
  memset(ou,0,sizeof(ou));
  memset(dn,0,sizeof(dn));
  int l[t],r[t],x[t];
  for(int i=0;i<t;i++) cin>>l[i]>>r[i]>>x[i];
  for(int i=0;i<t;i++){
    l[i]--;
    int p=0;
    while(BS*p<=l[i]) p++;
    eval(p-1);
    for(int j=l[i];j<min(r[i],BS*p);j++){
      if(ou[j/BS]) break;
      if(dn[j]==x[i]-1) dn[j]=x[i];
      else dn[j]=-1;
    }
    for(;BS*(p+1)<=r[i];p++){
      if(ou[p]) continue;
      if(up[p]){
	if(to[p]==x[i]-1) to[p]=x[i];
	else ou[p]=1;
      }else{
	up[p]=1;
	fr[p]=x[i]-1;
	to[p]=x[i];
      }
    }
    eval(p);
    for(int j=BS*p;j<r[i];j++){
      if(ou[j/BS]) break;
      if(dn[j]==x[i]-1) dn[j]=x[i];
      else dn[j]=-1;
    }
  }
  int p=0;
  while(BS*p<n) eval(p++);
  int ans=0;
  for(int j=0;j<n;j++){
    if(ou[j/BS]) continue;
    ans+=dn[j]==k;
  }
  cout<<ans<<endl;
  return 0;
}