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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

struct inv{
  int l,r; //closed interval
  inv(int a=0,int b=0):l(a),r(b){}
  inv operator+=(inv x){
    if(l==0 && r==0)l = x.l, r = x.r;
    else if(r+1==x.l)r = x.r;
    else l=-1,r=-1;
    return *this;
  }
  bool operator==(inv x){ return l==x.l && r==x.r; }
  bool operator!=(inv x){ return l!=x.l || r!=x.r; }
};

class SegmentTree{
  int n;
  vector<inv> node;
public:
  SegmentTree(int n_){
    n = 1;
    while(n<n_)n*=2;

    node.resize(2*n-1);
    for(int i=0;i<2*n-1;i++)node[i] = inv(0,0);
  }

  inv get(int x){
    x += n-1;
    inv res = node[x];
    while(x){
      x = (x-1)/2;
      if(node[x] != inv(0,0)){
	res += node[x];
      }
    }
    return res;
  }

  void add(int l, int r, inv x){
    add(l,r,x,0,n,0);
  }

  void add(int l, int r, inv x, int a, int b, int k){
    if(r<=a || b<=l)return;
    if(l<=a && b<=r){
      node[k] += x;
      return;
    }

    if(node[k] != inv(0,0)){
      add(a,(a+b)/2,node[k],a,(a+b)/2,2*k+1);
      add((a+b)/2,b,node[k],(a+b)/2,b,2*k+2);
    }

    add(l,r,x,a,(a+b)/2,2*k+1);
    add(l,r,x,(a+b)/2,b,2*k+2);
    node[k] = inv(0,0);
  }
};

int main(){
  int n,k,t;
  cin >> n >> k >> t;

  SegmentTree st(n);

  for(int i=0;i<t;i++){
    int l,r,x;
    cin >> l >> r >> x; l--;
    st.add(l,r,inv(x,x));
  }

  int ans = 0;
  for(int i=0;i<n;i++){
    if(st.get(i) == inv(1,k))ans++;
  }
  cout << ans << endl;
}