oj.uz

Submission #330813

# Submission time Handle Problem Language Result Execution time Memory
330813 2020-11-26T16:15:44 Z jungsnow Fuel Station (NOI20_fuelstation) C++14
13 / 100
 313 ms 9876 KB 
#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 = 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);
    T.upd(1, 1, M, mp[D], mp[D], 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
0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 9836 KB Output is correct
2 Correct 286 ms 9708 KB Output is correct
3 Correct 288 ms 9708 KB Output is correct
4 Correct 199 ms 7532 KB Output is correct
5 Correct 197 ms 7532 KB Output is correct
6 Correct 286 ms 9836 KB Output is correct
7 Correct 288 ms 9836 KB Output is correct
8 Correct 197 ms 7532 KB Output is correct
9 Correct 313 ms 9876 KB Output is correct
10 Correct 197 ms 7532 KB Output is correct
11 Correct 289 ms 9708 KB Output is correct
12 Correct 198 ms 7532 KB Output is correct
13 Correct 287 ms 9708 KB Output is correct
14 Correct 287 ms 9708 KB Output is correct
15 Correct 198 ms 7660 KB Output is correct
16 Correct 295 ms 9708 KB Output is correct
17 Correct 198 ms 7532 KB Output is correct
18 Correct 297 ms 9708 KB Output is correct
19 Correct 198 ms 7660 KB Output is correct
20 Correct 303 ms 9708 KB Output is correct

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 0 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 0 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 0 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -