代码
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//优先队列维护价格最低的加油站
struct ST{
int c,i;//价格 编号
friend bool operator < (const ST &a, const ST &b){ return a.c>b.c; }
};
int l[200001]; //每个加油站剩余油量
priority_queue<ST> q;
int closed=-1; //i<=closed 加油站i无效
//单调队列维护路径上最小的邮箱剩余大小
struct N{
int v,i; //经过第i个加油站时邮箱剩余大小为v
}s[200001];
int h=0, t=0;//单调队列头尾指针,当前元素大于队尾则放入队尾,小于队尾则队尾出列,放入队尾
long long an = 0;
int find(int a, int b, int i){ //二分查找
if (a==b) return a;
int mid = (a+b)/2;
if (s[mid].i>=i){
return find(a, mid, i);
}else{
return find(mid+1, b, i);
}
}
int find2(int a, int b, int v){ //二分查找
if (a==b) return a;
int mid = (a+b)/2;
if (s[mid].v<v){
return find2(mid+1, b, v);
}else{
return find2(a, mid, v);
}
}
int get(int need){
int o = 0;
while (!q.empty() && t-h>0){
ST tp = q.top();
if (tp.i>closed && l[tp.i]>0){
//找到[tp.i, now)最小邮箱剩余大小的加油站i
int i = find(h, t-1, tp.i);
int oc = min(min(need, l[tp.i]), s[i].v); //加油量不会超过i的最小邮箱剩余大小s[i].v,
l[tp.i] -= oc;
need -= oc;
//维护优先队列
for (int j=i;j<t;j++) s[j].v -= oc;
if (s[i].v==0) {
closed = s[i].i;
h = i+1;
}else{
//查找i之前第一个大于等于s[i].v的站号j,维护单调队列
if (i!=h){
int j = find2(h, i-1, s[i].v);
if (s[j].v>=s[i].v){
int k = 0;
while (i+k<t){
s[j+k] = s[i+k];
k++;
}
t = j+k;
}
}
}
o += oc;
an += (long long)(tp.c) * oc;
if (!need) return o;
}
q.pop();
}
return o;
}
int main(){
int n, m;
cin >> n >> m;
int d, p=m; //p:当前邮箱剩余油量
for (int i=0;i<n;i++){
ST st;
scanf("%d%d%d",&d,&st.c,&l[i]);
//根据还需要的油量取油
while (p<d){
int add = get(min(d-p, m-p));
if (!add){
cout << -1; return 0;
}
p+=add;
}
p-=d;
//将新的站加入优先队列
st.i=i;
q.push(st);
//维护单调队列
while (t-h>0 && s[t-1].v>=m-p) t--;
s[t].v=m-p; s[t++].i=i;
}
cout << an << endl;
return 0;
}