Problem: Example

Input

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


Output

1

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
const pii invalid(-100, -100);
const pii neutral(-1, -1);
pii merge(const pii &a, const pii &b){
    if(a.second + 1 == b.first){
        return pii(a.first, b.second);
    }
    return invalid;
}

int main(){
    int n,k,t;
    cin >> n >> k >> t;
    const int siz = 512;
    vector<pii> bucket(n/siz + 1, neutral);
    vector<pii> cell(n, pii(0, 0));
    for(int i=0; i<t; i++){
        int l,r,x;
        cin >> l >> r >> x;
        l--; //[l, r), 0-idx
        int lmin=l-l%siz, rmin=r-1-(r-1)%siz;
        int lmax=lmin+siz, rmax=rmin+siz;
        vector<pii> range{pii(lmin, lmax)};
        if(lmin < rmin){
            range.emplace_back(rmin, rmax);
        }
        for(auto ra: range){
            for(int j=ra.first; j<ra.second; j++){
                if(bucket[j/siz] != neutral){
                    cell[j] = merge(cell[j], bucket[j/siz]);
                }
                if(l<=j and j<r){
                    cell[j] = merge(cell[j], pii(x, x));
                }
            }
            bucket[ra.first/siz] = neutral;
        }
        for(int j=lmax/siz; j<rmin/siz; j++){
            if(bucket[j] == neutral){
                bucket[j] = pii(x, x);
            }else{
                bucket[j] = merge(bucket[j], pii(x, x));
            }
        }
    }

    int ans = 0;
    for(int i=0; i<n; i++){
        if(bucket[i/siz] != neutral){
            cell[i] = merge(cell[i], bucket[i/siz]);
        }
        if(cell[i] == pii(0, k)){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}