Submission #1265524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265524		phtung	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	276 ms	36252 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,0), lazy(4*n,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;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D;
    cin >> N >> D;

    vector<Station> st(N);
    for (int i=0; i<N; i++) cin >> st[i].x >> st[i].a >> st[i].b;

    st.push_back({(int)D, 0, D, 0});
    int M = N+1;

    sort(st.begin(), st.end(), [](auto &u, auto &v){ return u.x < v.x; });
    for (int i=0; i<M; i++) st[i].ix = i;

    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;
    });

    vector<long long> uniqB;
    for (int id : ord) {
        if (uniqB.empty() || uniqB.back() != st[id].b)
            uniqB.push_back(st[id].b);
    }

    long long F = uniqB[0];
    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);

    for (int i=0; i<M; i++) {
        if (i+1 <= M-1 && st[i].a)
            seg.add(1, 0, M-1, i+1, M-1, st[i].a);
    }

    int ptr = 0;
    while (ptr<M && st[ord[ptr]].b == F) ++ptr;

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

    int last_cut = 0;
    for (size_t t=1; t<uniqB.size(); t++) {
        long long nextF = uniqB[t];
        long long delta = nextF - F;

        seg.add(1, 0, M-1, 0, M-1, delta);

        for (int k=last_cut; k<ptr; k++) {
            int i = ord[k], L = st[i].ix + 1;
            if (L <= M-1 && st[i].a)
                seg.add(1, 0, M-1, L, M-1, -st[i].a);
        }
        last_cut = ptr;

        while (ptr<M && st[ord[ptr]].b == nextF) ++ptr;
        F = nextF;

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

    cout << F - seg.getMin() << "\n";
}

• 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