TOI13: Chromatography Art

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef tuple<int, int, int, int> tpp;

const int N = 1e6;

vector<tpp> events;
int fenwick[N + 2];

void update(int i, int x){
    for(; i <= N + 1; i += (i & -i)){
        fenwick[i] += x;
    }
}

int getSum(int i){
    int sum = 0;
    for(; i >= 1; i -= (i & -i)){
        sum += fenwick[i];
    }
    return sum;
}

int main(){

    int nPaint, tr;
    scanf("%d%d", &nPaint, &tr);
    for(int i = 1; i <= nPaint; ++i){
        int l, height, length, color;
        scanf("%d%d%d%d", &l, &height, &length, &color);
        events.emplace_back(l, height, color, 1);
        events.emplace_back(l + length, height, color, 2);
    }
    sort(events.begin(), events.end());

    int last = 0;
    lli sum = 0;
    for(tpp e : events){
        int pos = get<0>(e);
        int height = get<1>(e);
        int color = get<2>(e);
        int add = get<3>(e);
        if(pos != last){ // Calculate Old Status
            // Lower Bound
            int l = 1;
            int r = 1e6 + 1;
            int lwb = 1e6 + 1;
            while(l <= r){
                int m = (l + r) / 2;
                if(getSum(m) <= tr){
                    lwb = min(lwb, m);
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            // Upper Bound
            l = 1;
            r = 1e6 + 1;
            int upb = 1e6 + 1;
            while(l <= r){
                int m = (l + r) / 2;
                if(getSum(m) < tr){
                    upb = min(upb, m);
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            // Calculate Number of tr
            if(getSum(lwb) == tr){
                sum += (upb - lwb) * (pos - last);
            }
            last = pos;
        }
        if(add == 1){
            update(1, color);
            update(height + 1, -color);
        } else if(add == 2){
            update(1, -color);
            update(height + 1, color);
        }
    }
    cout << sum;

    return 0;
}