P1607 [USACO09FEB] Fair Shuttle G

可以将所有组按照左端点排序。

如果当前的左端点大于等于某些在车上的牛，那他们就下车，答案增加。

然后，我们考虑插入这一组奶牛，我们发现同样是奶牛，我们肯定希望越早下车越好，这样可以为后面的牛腾出更多的空间，所以我们对于当前的这组牛，若放不下，我们试图删除当前下车时间最晚的一批牛（此时需要保证删除这批牛之后空间 \(\le\) 当前所需的空间），重复执行。

然后，我们遇到的局面有两类：

1. 没有牛了，此时我们直接插入当前牛（注意不超过容量）。
2. 还有牛，此时删除这批牛之后空间 \(>\) 当前所需的空间，那么我们只需要删除至恰好可以放下当前的这批牛（如果多删除，会导致错误。比如后面没有牛了）。

我们考虑用 set 维护，每次从小到大删除离开时间小于等于当前时刻的牛，从大到小删除更劣的牛。（其实有一个叫做双端堆的东西，之前想搞但是很难写）。

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=100010;
int n,c;
struct segment{
    int l,r,t;
    bool operator<(segment&A){
        return l<A.l;
    }
}seg[N];
struct cow{
    int r,t;
    bool operator<(const cow &A)const{
        return r>A.r;
    }
};
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d%*d%d",&n,&c);
    E(i, n){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        seg[i]={a,b,c};
    }
    sort(seg+1,seg+1+n);
    int ans=0,tot=0;
    multiset<cow>s;
    cow it;
    E(i, n){
        auto[l,r,t]=seg[i];
        Wh(!s.empty()&&(it=*s.rbegin()).r<=l){
            ans+=it.t;
            tot-=it.t;
            s.erase(prev(s.end()));
        }
        Wh(!s.empty()&&(it=*s.begin()).r>=r&&c-tot+it.t<=t){
            s.erase(s.begin());
            tot-=it.t;
        }
        if(!s.empty()&&(it=*s.begin()).r>=r&&c-tot+it.t>t&&c-tot<t){
            s.erase(s.begin());
            s.insert({it.r,it.t-(t-(c-tot))});
            tot-=t-(c-tot);
        }
        s.insert({r,min(c-tot,t)});
        tot+=min(c-tot,t);
    }
    Wh(!s.empty())ans+=(*s.begin()).t,s.erase(s.begin());
    printf("%d",ans);
    return 0;
}