Problem: Example

Input

3 2
3
1 2 1
2 3 2
3 3 1


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

typedef pair<int, int>P;

P tree[524300];
void update(int id, int d, int l, int r, int a, int b){
    int L = (id<<d) - 262144;
    int R = (id<<d) + (1<<d) - 1 - 262144;
    if(r < L || R < l)return;
    if(l<=L && R<=r){
        if(tree[id].first==0){
            tree[id].first = a;
            tree[id].second = b;
            //cout<<L<<" "<<R<<" -> "<<tree[id].first<<" "<<tree[id].second<<endl;
        }
        else if(tree[id].second+1==a){
            tree[id].second = b;
            //cout<<L<<" "<<R<<" -> "<<tree[id].first<<" "<<tree[id].second<<endl;
        }
        else{
            tree[id] = P(999999, 999999);
            //cout<<L<<" "<<R<<" -> "<<tree[id].first<<" "<<tree[id].second<<endl;
        }
    }
    else if(tree[id].first==999999){

    }
    else if(tree[id].first==0){
        update(id*2, d-1, l, r, a, b);
        update(id*2+1, d-1, l, r, a, b);
    }
    else{
        update(id*2, d-1,L,R,tree[id].first,tree[id].second);
        update(id*2+1, d-1,L,R,tree[id].first,tree[id].second);
        tree[id].first = 0;
        tree[id].second = 0;
        //cout<<L<<" "<<R<<" -> "<<tree[id].first<<" "<<tree[id].second<<endl;
        update(id*2, d-1, l, r, a, b);
        update(id*2+1, d-1, l, r, a, b);
    }
}

P check(int id, P p){
    if(id==0)return p;
    if(tree[id].first!=0){
        //cout<<tree[id].first<<" "<<tree[id].second<<endl;
        if(p.first==0){
            p=tree[id];
        }
        else if(p.second+1==tree[id].first){
            p.second=tree[id].second;
        }
        else{
            p = P(999999, 999999);
        }
    }
    return check(id/2, p);
}

int main(){
    int N, K, T;
    cin>>N>>K>>T;
    for(int i=0;i<T;i++){
        int l, r, x;
        cin>>l>>r>>x;
        update(1, 18, l, r, x, x);
    }
    int ans = 0;
    for(int i=1;i<=N;i++){
        P p = check(262144+i, P(0, 0));
        //cout<<i<<" : "<<p.first<<" "<<p.second<<endl;
        if(p.first==1 && p.second==K)ans++;
    }
    cout<<ans<<endl;

    return 0;
}