46分求调
查看原帖
46分求调
1476569
L0_0楼主2025/6/21 21:32

为什么只有 4646

#include<bits/stdc++.h>
using namespace std;
const int N = 8e4+1;
int k, n, c;
struct Node{
    int l, r, m;
    bool operator<(const Node &i) const {return r < i.r;}
};
vector<Node> v;
int mn[N], tag[N];
void pushup(int p){mn[p] = min(mn[p*2], mn[p*2+1]);}
void down(int p, int t){
    tag[p] -= t;
    mn[p] -= t;
}
void update(int p, int l, int r, int s, int t, int k){
    // 区间 减 k
    if (s <= l && r <= t){
        down(p, k);
        return;
    }
    int mid = l + r >> 1;
    down(p*2, tag[p]);
    down(p*2+1, tag[p]);
    tag[p] = 0;
    if (s <= mid) update(p*2, l, mid, s, t, k);
    if (t > mid) update(p*2+1,mid+1,r,s,t,k);
    pushup(p);
}
int query(int p,int l,int r,int s,int t){
    if (s<=l && r<=t) return mn[p];
    int mid = l + r >> 1;
    down(p*2, tag[p]);
    down(p*2+1, tag[p]);
    tag[p] = 0;
    int ans = 1e9;
    if (s<=mid) ans = query(p*2,l,mid,s,t);
    if (t>mid) ans = min(ans,query(p*2+1,mid+1,r,s,t));
    return ans;
}
long long ans;

int main(){
    cin>>k>>n>>c;
    v.resize(k);
    for(int i=0;i<k;i++) cin >> v[i].l >> v[i].r >> v[i].m;
    sort(v.begin(), v.end());
    for(int i=0;i<N;i++) mn[i] = c;
    for(auto [l,r,m]:v){
        int t = query(1,1,n,l,r-1);
        t = min(t, m);
        ans += t;
        update(1,1,n,l,r-1,t);
    }
    cout << ans;
}
2025/6/21 21:32
加载中...