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;

/*RMQ  update:O(logN)  query:O(lonN)*/
const int MAX_N = 1<<20;

struct data{
  int l,r;
};

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

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

//[a,b)
//query(a,b,0,0,n)
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{
    if(dat[k].l){
      if(!dat[k*2+1].l)dat[k*2+1].l=dat[k].l,dat[k*2+1].r=dat[k].r;
      else if(dat[k*2+1].r+1==dat[k].l)dat[k*2+1].r=dat[k].r;
      else dat[k*2+1].l=dat[k*2+1].r=-1;
      if(!dat[k*2+2].l)dat[k*2+2].l=dat[k].l,dat[k*2+2].r=dat[k].r;
      else if(dat[k*2+2].r+1==dat[k].l)dat[k*2+2].r=dat[k].r;
      else dat[k*2+2].l=dat[k*2+2].r=-1;
      dat[k].l=dat[k].r=0;
    }
    query(a,b,k*2+1,l,(l+r)/2,x);
    query(a,b,k*2+2,(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;
}