oj.uz

Submission #330807

# Submission time Handle Problem Language Result Execution time Memory
330807 2020-11-26T16:08:35 Z jungsnow Fuel Station (NOI20_fuelstation) C++14
0 / 100
 311 ms 14596 KB 
#include<bits/stdc++.h>

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 = inf;
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);
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 14596 KB Output is correct
2 Incorrect 295 ms 14572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -