TOI13: art (Lazy)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
using pll  = pair <lli, lli>;
using plL = pair <lli, pll>;
using pLL = pair <pll, pll>;
const lli INF = 2e18;
lli tree[2*(1<<21)], lazy[2*(1<<21)];
lli n, t;

void Lazy(lli idx, lli l, lli r){
    tree[idx] += lazy[idx] * (r-l+1);
    if(l != r){
        lazy[2*idx] += lazy[idx];
        lazy[2*idx+1] += lazy[idx];
    }
    lazy[idx] = 0;
}

void update(lli idx, lli l, lli r, lli s, lli e, lli val){
    if(lazy[idx] != 0) Lazy(idx, l, r);
    if(l > e or r < s) return ;
    if(s <= l and r <= e){
        if(l != r){
            lazy[2*idx] += val;
            lazy[2*idx + 1] += val;
        }
        tree[idx] += val * (r-l+1);
        return ;
    }
    lli mid = (lli) (l + r)/ 2;
    update(2*idx, l, mid, s, e, val);
    update(2*idx + 1, mid + 1, r, s, e, val);
    tree[idx] = tree[2*idx] + tree[2*idx + 1];
}

lli query(lli idx, lli l, lli r, lli k){
    if(lazy[idx] != 0) Lazy(idx, l, r);
    if(l == r){
        return tree[idx];
    }
    lli mid = (lli) (l + r) / 2;
    if(k <= mid)
        return query(2*idx, l, mid, k);
    return query(2*idx+1, mid + 1, r, k);
}

lli Q(){
    lli l, r;
    lli mn = INF;
    l = 1, r = 1e6;
    while(l <= r){
        lli mid = (l + r) / 2;
        lli color = query(1, 1, 1e6, mid);
        if(color < t){
            r = mid - 1;
        }
        else if(color == t){
            mn = min(mn, mid);
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }

    lli mx = -INF;
    l = 1, r = 1e6;
    while(l <= r){
        lli mid = (l + r) / 2;
        lli color = query(1, 1, 1e6, mid);
        if(color < t){
            r = mid - 1;
        }
        else if(color == t){
            mx = max(mx, mid);
            l = mid + 1;
        }
        else {
            l = mid + 1;
        }
    }
    if(mn == INF or mx == -INF) return 0;
    return mx - mn + 1;
}

int main(){

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

    vector <plL> event;
    for(lli i = 1; i <= n; i ++){
        lli s, h, w, c;
        scanf("%lld%lld%lld%lld", &s, &h, &w, &c);
        event.push_back({s, {c, h}});
        event.push_back({s+w, {-1*c, h}});
    }

    sort(event.begin(), event.end());
    lli pre_x = -1; // x
    lli ans = 0; // t color area
    lli color = 0;

    for(auto e: event){
        lli x = e.first;
        lli c = e.second.first;
        lli y = e.second.second;
        if(pre_x == -1){
            pre_x = x;
            color += c;
            update(1, 1, 1e6, 1, y, c);
            continue;
        }
        // query -> update
        if(pre_x != x and color >= t) // query
            ans += (lli) Q() * (x - pre_x);
        // update
        update(1, 1, 1e6, 1, y, c);
        color += c;
        pre_x = x;
    }

    printf("%lld", ans);

    return 0;
}
/**
2 2
3 2 2 2
1 2 2 2

4 1
2 4 4 1
1 5 5 1
2 7 7 1
1 8 8 1

10 3
2 4 4 1
1 5 5 1
2 7 7 1
1 8 8 1
5 6 3 1
3 3 3 1
6 4 4 1
1 10 10 1
2 2 1 1
1 1 1 1
**/