oj.uz

Submission #888941

# Submission time Handle Problem Language Result Execution time Memory
888941 2023-12-18T12:44:27 Z adaawf Fuel Station (NOI20_fuelstation) C++14
13 / 100
 244 ms 44740 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct FUEL {
    long long int x, a, b;
} a[300005];
bool cmp(FUEL aa, FUEL bb) {
    return aa.x < bb.x;
}
long long int t[1200005], lazy[1200005];
void push(int v) {
    t[v * 2] += lazy[v];
    lazy[v * 2] += lazy[v];
    t[v * 2 + 1] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v] += x;
        lazy[v] += x;
        return;
    }
    push(v);
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, l, min(r, mid), x);
    update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
long long int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v];
    }
    push(v);
    int mid = (tl + tr) / 2;
    return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, d, c = 0, res = 1e18;
    cin >> n >> d;
    vector<pair<long long int, int>> v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].a >> a[i].b;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        v.push_back({a[i].b, i});
        update(1, 1, n, i, i, a[i].x);
    }
    sort(v.begin(), v.end(), greater<pair<long long int, int>>());
    res = d;
    for (auto w : v) {
        c += a[w.second].a;
        update(1, 1, n, w.second + 1, n, -a[w.second].a);
        long long int h = max(max(t[1], d - c), 0ll);
        res = min(res, h);
    }
    cout << res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 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 203 ms 43148 KB Output is correct
2 Correct 244 ms 44204 KB Output is correct
3 Correct 202 ms 44740 KB Output is correct
4 Correct 207 ms 43972 KB Output is correct
5 Correct 198 ms 43976 KB Output is correct
6 Correct 198 ms 42536 KB Output is correct
7 Correct 200 ms 44072 KB Output is correct
8 Correct 199 ms 44668 KB Output is correct
9 Correct 205 ms 44220 KB Output is correct
10 Correct 195 ms 42916 KB Output is correct
11 Correct 202 ms 44188 KB Output is correct
12 Correct 196 ms 44332 KB Output is correct
13 Correct 199 ms 44228 KB Output is correct
14 Correct 202 ms 44196 KB Output is correct
15 Correct 197 ms 43208 KB Output is correct
16 Correct 203 ms 44216 KB Output is correct
17 Correct 197 ms 44592 KB Output is correct
18 Correct 208 ms 43304 KB Output is correct
19 Correct 212 ms 43200 KB Output is correct
20 Correct 202 ms 44588 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 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 4440 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 4444 KB Output is correct
2 Incorrect 1 ms 4444 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 4444 KB Output is correct
2 Incorrect 1 ms 4444 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 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -