Submission #1265519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265519		phtung	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	241 ms	34492 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;

struct Seg {
    int n;
    vector<long long> mn, lazy;
    Seg(int n=0): n(n), mn(4*n+4, 0), lazy(4*n+4, 0) {}
    void push(int p){
        if(lazy[p]==0) return;
        for(int c:{p<<1,(p<<1)|1}){
            mn[c] += lazy[p];
            lazy[c] += lazy[p];
        }
        lazy[p]=0;
    }
    void build(int p,int l,int r, const vector<long long>& base){
        if(l==r){ mn[p]=base[l]; return; }
        int m=(l+r)>>1;
        build(p<<1,l,m,base);
        build((p<<1)|1,m+1,r,base);
        mn[p]=min(mn[p<<1],mn[(p<<1)|1]);
    }
    void add(int p,int l,int r,int ql,int qr,long long v){
        if(ql>r||qr<l) return;
        if(ql<=l&&r<=qr){ mn[p]+=v; lazy[p]+=v; return; }
        push(p);
        int m=(l+r)>>1;
        add(p<<1,l,m,ql,qr,v);
        add((p<<1)|1,m+1,r,ql,qr,v);
        mn[p]=min(mn[p<<1],mn[(p<<1)|1]);
    }
    long long getMin(){ return mn[1]; }
};

struct Station {
    int x; long long a, b;
    int ix; // index after sorting by x
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; long long D;
    if(!(cin>>N>>D)) return 0;
    vector<Station> st(N);
    for(int i=0;i<N;i++){
        cin>>st[i].x>>st[i].a>>st[i].b;
    }
    // add destination as a "station"
    st.push_back({(int)D, 0, D, 0});
    int M = N+1;

    // sort by X and give indices
    sort(st.begin(), st.end(), [](const Station& u, const Station& v){
        return u.x < v.x;
    });
    for(int i=0;i<M;i++) st[i].ix = i;

    // group by B (increasing) to know when stations drop out as F grows
    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){
        if(st[i].b != st[j].b) return st[i].b < st[j].b;
        return st[i].x < st[j].x;
    });

    // unique B values (in increasing order)
    vector<long long> uniqB;
    uniqB.reserve(M);
    for(int id: ord){
        if(uniqB.empty() || uniqB.back()!=st[id].b) uniqB.push_back(st[id].b);
    }

    long long F = uniqB.front(); // start at min B
    // base[i] = F - Xi
    vector<long long> base(M);
    for(int i=0;i<M;i++) base[i] = F - st[i].x;

    Seg seg(M);
    seg.build(1,0,M-1,base);

    // at F = minB, all stations are usable -> add Ai to (i+1..M-1)
    for(int i=0;i<M;i++){
        if(i+1<=M-1 && st[i].a!=0) seg.add(1,0,M-1,i+1,M-1, st[i].a);
    }

    // pointer over ord to know which stations’ B == current F
    int ptr = 0;
    while(ptr < M && st[ord[ptr]].b == F) ++ptr;

    // check
    if(seg.getMin() >= 0){
        long long ans = F - seg.getMin(); // F' = F - min(Frem)
        cout << ans << "\n";
        return 0;
    }

    // increase F step-by-step to next B, dropping stations that become unusable
    for(size_t t=1; t<uniqB.size(); ++t){
        long long nextF = uniqB[t];
        long long delta = nextF - F;
        // add delta to ALL positions
        seg.add(1,0,M-1,0,M-1, delta);

        // all stations with B == F just became unusable when we pass to nextF
        // (those are ord[prev_ptr .. ptr-1]); subtract their contributions on (ix+1..M-1)
        int prev_ptr = ptr - 0;
        // move ptr to include all with B == nextF (but first we need to remove those with old F)
        // old group is: indices with B == F  -> that is ord[posOldL .. posOldR]
        // We didn't store posOldL; reconstruct as walk from start each time is O(M). Better: track ranges.
        // We already have 'ptr' at first id with B > F. We need range [last_cut .. ptr-1] as the old group.
        // Maintain last_cut.
        static int last_cut = 0;
        // remove old group (B == F)
        for(int k=last_cut; k<prev_ptr; ++k){
            int i = ord[k];
            int L = st[i].ix + 1;
            if(L<=M-1 && st[i].a!=0) seg.add(1,0,M-1, L, M-1, -st[i].a);
        }
        last_cut = prev_ptr;

        // advance ptr to first id with B > nextF (prepare for next round)
        while(ptr < M && st[ord[ptr]].b == nextF) ++ptr;

        F = nextF;

        if(seg.getMin() >= 0){
            long long ans = F - seg.getMin();
            cout << ans << "\n";
            return 0;
        }
    }

    // Nếu vẫn chưa đạt (trên lý thuyết sẽ đạt), dự phòng: tăng F đến khi đủ
    // (ở đây có thể F=D cũng đủ vì không cần dùng trạm nào)
    // Đảm bảo an toàn:
    long long need = -seg.getMin();
    cout << (F + need) << "\n";
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21