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;
const int MAX_N = 1<<20;

struct data{
  int l,r;
};

data dat[2*MAX_N-1];
int n;

void init(int n_){
  n=1;
  while(n<n_)n*=2;
  for(int i=0;i<2*n-1;i++)
    dat[i].l=dat[i].r=0;
}

void query(int a,int b,int k,int l,int r,int x){
  if(r<=a||b<=l)return;
  if(a<=l&&r<=b){
    if(!dat[k].l)dat[k].l=dat[k].r=x;
    else if(dat[k].r+1==x)dat[k].r=x;
    else dat[k].l=dat[k].r=-1;
  }else{
    int k1=k*2+1,k2=k*2+2;
    int L=dat[k].l,R=dat[k].r;
    if(L){
      if(!dat[k1].l)dat[k1].l=L,dat[k1].r=R;
      else if(dat[k1].r+1==L)dat[k1].r=R;
      else dat[k1].l=dat[k1].r=-1;
      if(!dat[k2].l)dat[k2].l=L,dat[k2].r=R;
      else if(dat[k2].r+1==L)dat[k2].r=R;
      else dat[k2].l=dat[k2].r=-1;
      dat[k].l=dat[k].r=0;
    }
    query(a,b,k1,l,(l+r)/2,x);
    query(a,b,k2,(l+r)/2,r,x);
  }
}

int main(){
  int k,t,l,r,x;
  cin>>n>>k>>t;
  init(n);
  for(int i=0;i<t;i++){
    scanf("%d%d%d",&l,&r,&x);
    l--,r--;
    query(l,r+1,0,0,n,x);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    query(i,i+1,0,0,n,k+1);
    if(dat[n+i-1].l==1&&dat[n+i-1].r==k+1)
      ans++;
  }
  cout<<ans<<endl;
  return 0;
}