Submission #337595

#	Time	Username	Problem	Language	Result	Execution time	Memory
337595		ncduy0303	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	547 ms	33004 KiB

FuelStation

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;

struct segtree { 
    struct tdata {
        ll mn, addval;
        tdata(): mn(), addval() {}
        tdata(ll val): mn(val), addval() {}
        tdata(tdata l, tdata r): mn(min(l.mn, r.mn)), addval() {}
    };
    int ln(int node) {return 2 * node;}
    int rn(int node) {return 2 * node + 1;}
    int n; vector<tdata> st;
    segtree(int n): n(n), st(4 * n) {}
    void apply(int node, int start, int end, ll val) {
        st[node].mn += val;
        st[node].addval += val;
    }
    void combine(int node) {
        st[node].mn = min(st[ln(node)].mn, st[rn(node)].mn);
    }
    void propagate(int node, int start, int end) {
        if (start == end || st[node].addval == 0) return;
        int mid = (start + end) / 2;
        apply(ln(node), start, mid, st[node].addval);
        apply(rn(node), mid + 1, end, st[node].addval);
        st[node].addval = 0;
    }
    void update(int node, int start, int end, int l, int r, ll val) {
        propagate(node, start, end);
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            apply(node, start, end, val);
            return;
        }
        int mid = (start + end) / 2;
        update(ln(node), start, mid, l, r, val);
        update(rn(node), mid + 1, end, l, r, val);
        combine(node);
    }
    tdata query(int node, int start, int end, int l, int r) {
        propagate(node, start, end);
        if (r < start || end < l) return tdata();
        if (l <= start && end <= r) return st[node];
        int mid = (start + end) / 2;
        return tdata(query(ln(node), start, mid, l, r), query(rn(node), mid + 1, end, l, r));
    }
    void update(int l, int r, ll val) {update(1, 0, n - 1, l, r, val);}
    tdata query(int l, int r) {return query(1, 0, n - 1, l, r);}
};

void solve() {
    int n, d; cin >> n >> d;
    vector<ar<int,3>> arr(n + 1); // {b, x, a}
    vector<int> pos(n + 1);
    for (int i = 0; i < n; i++) {
        int x, a, b; cin >> x >> a >> b;
        arr[i] = {b, x, a};
        pos[i] = x;
    }
    arr[n] = {d, d, 0};
    pos[n] = d;
    sort(arr.rbegin(), arr.rend());
    sort(pos.begin(), pos.end());
    segtree st(n + 1);
    for (int i = 0; i <= n; i++) {
        st.update(i, i, -pos[i]);
    }
    ll ans = INF, b_pre = 0;
    for (auto [b, x, a] : arr) {
        st.update(0, n, b - b_pre);
        int idx = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
        if (idx < n) st.update(idx + 1, n, a);
        ll left = st.query(0, n).mn;
        if (left >= 0) ans = min(ans, b - left);
        b_pre = b;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

• 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