Submission #1214477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214477		VMaksimoski008	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	593 ms	55608 KiB

FuelStation

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

struct segment_tree {
    int n;
    vector<ll> tree, lazy;

    segment_tree(int _n) : n(_n), tree(4*n, -1e18), lazy(4*n) {}

    void push(int u, int tl, int tr) {
        tree[u] += lazy[u];

        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }

        lazy[u] = 0;
    }

    void update(int u, int tl, int tr, int l, int r, ll v) {
        push(u, tl, tr);
        if(tl > r || l > tr) return ;

        if(l <= tl && tr <= r) {
            lazy[u] += v;
            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, v);
        update(2*u+1, tm+1, tr, l, r, v);
        tree[u] = max( tree[2*u], tree[2*u+1] );
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return -1e18;
        push(u, tl, tr);
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return max( query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r) );
    }

    void update(int l, int r, ll v) { update(1, 1, n, l, r, v); }
    ll query(int l, int r) { return query(1, 1, n, l, r); }
};

signed main() {
    int n, m; cin >> n >> m;
    vector<array<int, 3> > a(n+1);
    map<int, vector<int> > mp;
    for(int i=1; i<=n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    a.push_back({ m, 0, m });
    sort(a.begin()+1, a.end());
    for(int i=1; i<=n+1; i++)
        mp[-a[i][2]].push_back(i);

    ll ans = 1e9; n++;
    segment_tree sgt(n);
    for(auto [x, vec] : mp) {
        ll d = -x;
        for(int i : vec) {
            sgt.update(i, i, (ll)1e18 + a[i][0]);
            sgt.update(i+1, n, -a[i][1]);
        }
        ll mx = sgt.query(1, 1, n, 1, n);
        if(d >= mx) ans = min(ans, mx);
    }

    cout << ans << '\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