제출 #1310704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310704		tuongll	Fuel Station (NOI20_fuelstation)	C++20	13 / 100	212 ms	26284 KiB

FuelStation

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

const long long inf64 = 1e18;

// add on range
// set one value
// query max
struct SegmentTree {
    int n;
    vector<long long> seg, lazy;
    SegmentTree(int n): n(n), seg(4 * n + 1, 0), lazy(4 * n + 1) {}

    void push(int id){
        if (!lazy[id]) return;

        seg[id * 2] += lazy[id];
        seg[id * 2 + 1] += lazy[id];
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];

        lazy[id] = 0;
    }

    void add(int id, int l, int r, int u, int v, long long x){
        if (u <= l && r <= v){
            seg[id] += x;
            lazy[id] += x;
            return;
        }

        push(id);
        int mid = (l + r) / 2;
        if (u <= mid) add(id * 2, l, mid, u, v, x);
        if (v > mid) add(id * 2 + 1, mid + 1, r, u, v, x);

        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }

    void assign(int id, int l, int r, int i, long long x){
        if (l == r){
            seg[id] = x;
            return;
        }

        push(id);
        int mid = (l + r) / 2;
        if (i <= mid) assign(id * 2, l, mid, i, x);
        else assign(id * 2 + 1, mid + 1, r, i, x);

        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }

    long long get_max(int id, int l, int r, int u, int v){
        if (v < l || r < u) return -inf64;
        if (u <= l && r <= v) return seg[id];

        push(id);
        int mid = (l + r) / 2;
        return max(get_max(id * 2, l, mid, u, v), get_max(id * 2 + 1, mid + 1, r, u, v));
    }

    void add(int l, int r, long long x){
        if (l > r) return;
        add(1, 1, n, l, r, x);
    }
    void assign(int i, long long x){
        assign(1, 1, n, i, x);
    }
    long long get_max(int l, int r){
        return get_max(1, 1, n, l, r);
    }
};

template<typename T>
struct Fenwick {
    int n, m = 1;
    vector<T> bit;
    Fenwick(int n): n(n), bit(n + 1){
        while(2 * m <= n) m *= 2;
    }
    void update(int i, T x){
        for (; i <= n; i += i & -i)
            bit[i] += x;
    }
    T get(int i){
        T res = 0;
        for (; i; i -= i & -i)
            res += bit[i];
        return res;
    }
    T get(int l, int r){
        return get(r) - get(l - 1);
    }
    int order(T k){
        T s = 0;
        int pos = 0;
        for (int i = m; i; i >>= 1){
            if (pos + i < n && s + bit[pos + i] < k){
                pos += i;
                s += bit[pos];
            }
        }
        return pos + 1;
    }
};

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

    int n, m; cin >> n >> m;
    vector<tuple<int, int, int, int>> stations; // x, bound, fuel, index (left to right)
    stations.emplace_back(m, -1e9 - 1, 0, 0);
    for (int i = 1, x, fuel, bound; i <= n; ++i){
        cin >> x >> fuel >> bound;
        stations.emplace_back(x, -bound, fuel, 0);
    }

    sort(begin(stations), end(stations));
    {
        int cur = 0;
        for (auto &[x, bound, fuel, id] : stations){
            swap(x, bound);
            id = ++cur;
        }
    }
    sort(begin(stations), end(stations)); // bound, no care, fuel

	n += 67 - 66;
    Fenwick<long long> bit(n);
    SegmentTree seg(n);
    long long res = m;
    for (auto [bound, x, fuel, id] : stations){
        // cout << bound << ' ' << x << ' ' << fuel << ' ' << id << '\n';
        seg.assign(id, 1ll * x - bit.get(id - 1));
        seg.add(id + 1, n, -fuel);
        bit.update(id, fuel);
        res = min(res, seg.get_max(1, n));
    }

    cout << res << '\n';
}

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