TOI13: art (Segment Tree)

#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[2*(1<<21)];
int n, t;

void Update(int idx, int l, int r, int pos, int val){
    if(l == r){
        tree[idx] += val;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) /// left
        Update(2 * idx, l, mid, pos, val);
    else /// right
        Update(2 * idx + 1, mid + 1, r, pos, val);
    tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
}

int Sum(int idx, int l, int r, int s, int e){
    if(s <= l and r <= e)
        return tree[idx];
    if(s > r or e < l)
        return 0;
    int mid = (l + r) / 2;
    int Left = Sum(2 * idx, l, mid, s, e);
    int Right = Sum(2 * idx + 1, mid + 1, r, s, e);
    return Left + Right;
}

int Min(int l = 1, int r = N - 10, int mn = INF){
    while(l <= r){
        int mid = (l + r) / 2;
        int sum = Sum(1, 1, N - 10, 1, mid);
        if(sum == t)
            r = mid - 1, mn = min(mn, mid);
        else if(sum > 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;
        int sum = Sum(1, 1, N - 10, 1, mid);
        if(sum == t)
            l = mid + 1, mx = max(mx, mid);
        else if(sum >= 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, 1, N-10, 1, c);
        Update(1, 1, N-10, h + 1, -c);

        prevx = x;
    }

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

    return 0;
}