oj.uz

Submission #331446

# Submission time Handle Problem Language Result Execution time Memory
331446 2020-11-28T13:56:35 Z two_sides Fuel Station (NOI20_fuelstation) C++17
7 / 100
 255 ms 35820 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 3e5 + 5;

struct station {
    int x, a, b;
};

struct segtree {
    static const ll INF = LLONG_MAX;

    vector <ll> val, tag;
    int lo, hi, n; ll v;

    segtree(int n): n(n) {
        val.resize(n * 4 + 10);
        tag.resize(n * 4 + 10);
    }

    void push_tag(int i, ll tg) {
        val[i] += tg; tag[i] += tg;
    }

    void push_down(int i) {
        push_tag(i * 2, tag[i]);
        push_tag(i * 2 + 1, tag[i]);
        tag[i] = 0;
    }

    void update(int i, int l, int r) {
        if (l > hi || r < lo) return;
        if (l >= lo && r <= hi)
            return push_tag(i, v);
        push_down(i);
        int m = (l + r) / 2;
        update(i * 2, l, m);
        update(i * 2 + 1, m + 1, r);
        val[i] = min(val[i * 2],
        val[i * 2 + 1]);
    }

    void query(int i, int l, int r) {
        if (l > hi || r < lo) return;
        if (l >= lo && r <= hi) {
            v = min(v, val[i]); return;
        }
        push_down(i);
        int m = (l + r) / 2;
        query(i * 2, l, m);
        query(i * 2 + 1, m + 1, r);
    }

    void update(int lo, int hi, ll v) {
        if (lo > hi) return;
        this->lo = lo; this->hi = hi;
        this->v = v; update(1, 0, n);
    }

    ll query(int lo, int hi) {
        if (lo > hi) return INF;
        this->lo = lo; this->hi = hi;
        v = INF; query(1, 0, n);
        return v;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, d; cin >> n >> d;
    vector <station> ff(n);
    vector <int> nxt(n + 1);
    segtree st(n);
    for (station &s : ff)
        cin >> s.x >> s.a >> s.b;
    ff.push_back({d, 0, d});
    sort(ff.begin(), ff.end(),
    [](station p, station q) {
        return p.x < q.x;
    });
    int j = 0;
    for (int i = 0; i <= n; i++) {
        while (j < n &&
        ff[j].x == ff[i].x) j++;
        nxt[i] = j;
    }
    vector <int> od(n + 1);
    iota(od.begin(), od.end(), 0);
    sort(od.begin(), od.end(),
    [&](int i, int j) {
        return ff[i].b < ff[j].b;
    });
    j = 0;
    for (int i = 0; i <= n; i++)
        st.update(i, i, -ll(ff[i].x));
    for (int i = 0; i <= n; i++) {
        st.update(0, n, ll(ff[od[i]].b)
        - (i ? ff[od[i - 1]].b : 0));
        while (j < i && ff[od[j]].b < ff[od[i]].b)
            st.update(nxt[od[i]], n, -ll(ff[od[j++]].a));
        st.update(nxt[od[i]], n, ll(ff[od[i]].a));
        if (st.val[1] >= 0) {
            cout << ff[od[i]].b - st.val[1];
            return 0;
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1388 KB Output is correct
3 Incorrect 7 ms 1388 KB Output isn't correct
4 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 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Incorrect 1 ms 364 KB Output isn't correct
18 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 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 7 ms 1388 KB Output is correct
18 Incorrect 7 ms 1388 KB Output isn't correct
19 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 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Incorrect 255 ms 35820 KB Output isn't correct
17 Halted 0 ms 0 KB -