TOI13: art (Fenwick)

#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second
using lli = long long;
using pi = pair <int, int>;
using piI = pair <int, pi>;
const int N = 1e6 + 10;
const int INF = 1e9;
vector <piI> event;
int tree[N];
int n, t;

void Update(int pos, int val){
    for(int i = pos; i <= N - 10; i += i & -i)
        tree[i] += val;
}

int Sum(int pos, int sum = 0){
    for(int i = pos; i > 0; i -= i & -i)
        sum += tree[i];
    return sum;
}

int Min(int l = 1, int r = N - 10, int mn = INF){
    while(l <= r){
        int mid = (l + r) / 2;
        if(Sum(mid) == t)
            r = mid - 1, mn = min(mn, mid);
        else if(Sum(mid) > t)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return mn;
}

int Max(int l = 1, int r = N - 10, int mx = -INF){
    while(l <= r){
        int mid = (l + r) / 2;
        if(Sum(mid) == t)
            l = mid + 1, mx = max(mx, mid);
        else if(Sum(mid) >= t)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return mx;
}

int Cal(){
    int mn = Min();
    if(mn == INF) return 0;
    int mx = Max();
    return mx - mn + 1;
}

int main(){

    scanf("%d%d", &n, &t);

    for(int i=1;i<=n;i++){
        int s, h, w, o;
        scanf("%d%d%d%d", &s, &h, &w, &o);
        event.push_back({ s , {h, o} });
        event.push_back({ s + w , {h, -o} });
    }

    sort(event.begin(), event.end());

    int prevx = -1, prevh = -1;
    lli ans = 0;
    for(auto e: event){
        int x = e.F;
        int h = e.S.F;
        int c = e.S.S;

        if(prevx != -1)
            ans += (lli)( (lli)(x - prevx) * (lli)Cal() );

        Update(1, c);
        Update(h + 1, -c);

        prevx = x;
    }

    printf("%lld\n", ans);

    return 0;
}