Submission #330814

#	Time	Username	Problem	Language	Result	Execution time	Memory
330814		jungsnow	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	1118 ms	70684 KiB

FuelStation

#include<bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;

const int maxn = 300100;
const ll inf = 1e18;

struct sta {
    int A, B, X;
    sta() {}
    sta(int A, int B, int X) : A(A), B(B), X(X) {}
    bool operator < (const sta &other) const {
        return B > other.B;
    }
};

struct ST {
    int N;
    vector<ll> lazy;
    vector<ll> st;
    ST(int N = 0) : N(N), lazy(N << 2), st(N << 2) {}
    void pop(int v) {
        st[v] = max(st[v << 1], st[v << 1 | 1]);
    }
    void apply(int v, int lz) {
        lazy[v] += lz;
        st[v] += lz;
    }
    void push(int v) {
        if (lazy[v]) {
            apply(v << 1, lazy[v]);
            apply(v << 1 | 1, lazy[v]);
        }
        lazy[v] = 0;
    }
    void upd(int v, int l, int r, int x, int y, int val) {
        if (l > r || l > y || r < x) return;
        if (x <= l && r <= y) {
            apply(v, val);
            return;
        }
        int md = (l + r) >> 1;
        push(v);
        upd(v << 1, l, md, x, y, val);
        upd(v << 1 | 1, md + 1, r, x, y, val);
        pop(v);
    }
};

int N, M, D, id[maxn];
bool on[maxn];
ll Ans;
sta V[maxn];

signed main() {
//    freopen("cc.inp", "r", stdin);
//    freopen("cc.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> D;
    set<int> S;
    for (int i = 1; i <= N; ++i) {
        cin >> V[i].X >> V[i].A >> V[i].B;
        S.insert(V[i].X);
    }
    S.insert(D);
    map<int, int> mp;
    for (auto it = S.begin(); it != S.end(); ++it) {
        mp[*it] = ++M;
        id[M] = *it;
    }
    for (int i = 1; i <= N; ++i) {
        V[i].X = mp[V[i].X];
    }
    sort(V + 1, V + 1 + N);
    ST T(M);
    T.upd(1, 1, M, mp[D], mp[D], D);
    Ans = D;
    for (int i = 1; i <= N; ++i) {
        if (!on[V[i].X]) {
            T.upd(1, 1, M, V[i].X, V[i].X, id[V[i].X]);
            on[V[i].X] = 1;
        }
        T.upd(1, 1, M, V[i].X + 1, M, -V[i].A);
        ll Tm = T.st[1];
        if (Tm > V[i].B) continue;
        Ans = min(Ans, Tm);
    }
    cout << Ans;
    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