Submission #959129

#	Time	Username	Problem	Language	Result	Execution time	Memory
959129		Blagoj	Pinball (JOI14_pinball)	C++17	0 / 100	2 ms	3416 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

struct SegmentTree {
    vector<ll> sgt;

    SegmentTree(int mxn) {
        sgt.resize(4 * mxn, 1e16);
    }

    void reset() {
        for (int i = 0; i < sgt.size(); i++) sgt[i] = 1e16;
    }

    void update(int k, int l, int r, int i, ll val) {
        if (l > i || r < i) return;
        if (l == r) {
            sgt[k] = val;
            return;
        } 
        int mid = (l + r) / 2;
        update(k * 2, l, mid, i, val);
        update(k * 2 + 1, mid + 1, r, i, val);
        sgt[k] = min(sgt[k * 2], sgt[k * 2 + 1]);
    }

    ll get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 1e16;
        if (i <= l && r <= j) return sgt[k];
        int mid = (l + r) / 2;
        return min(get(k * 2, l, mid, i, j), get(k * 2 + 1, mid + 1, r, i, j));
    }
} sgt(1e5 + 10);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(n), c(n), d(n);
    set<ll> points;
    points.insert(1);
    points.insert(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        points.insert(a[i]);
        points.insert(b[i]);
        points.insert(c[i]);
    }
    unordered_map<ll, ll> h;
    int cnt = 0;
    for (auto x : points) h[x] = cnt++;
    sgt.update(1, 0, cnt - 1, h[1], 0);
    ll lCost[n], rCost[n];
    for (int i = 0; i < n; i++) {
        lCost[i] = sgt.get(1, 0, cnt - 1, h[a[i]], h[b[i]]);
        sgt.update(1, 0, cnt - 1, h[c[i]], lCost[i] + d[i]);
    }
    sgt.reset();
    sgt.update(1, 0, cnt - 1, h[m], 0);
    for (int i = 0; i < n; i++) {
        rCost[i] = sgt.get(1, 0, cnt - 1, h[a[i]], h[b[i]]);
        sgt.update(1, 0, cnt - 1, h[c[i]], rCost[i] + d[i]);
    }
    ll ans = 1e16;
    for (int i = 0; i < n; i++) ans = min(ans, lCost[i] + d[i] + rCost[i]);
    cout << (ans != 1e16 ? ans : -1);
}

Compilation message (stderr)

pinball.cpp: In member function 'void SegmentTree::reset()':
pinball.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int i = 0; i < sgt.size(); i++) sgt[i] = 1e16;
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49