Submission #958984

#	Time	Username	Problem	Language	Result	Execution time	Memory
958984		typ_ik	Pinball (JOI14_pinball)	C++17	100 / 100	499 ms	42704 KiB

pinball

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 300100;
int l[N], r[N], c[N], d[N];

ll pref[N], suf[N];
const ll INF = 1e16 + 128;

ll mn[2][4 * N];

ll get_min(bool where, int l, int r, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return INF;
    if (l <= tl && tr <= r)
        return mn[where][v];
    int tm = (tl + tr) >> 1;
    return min(get_min(where, l, r, v << 1, tl, tm),
               get_min(where, l, r, v << 1 | 1, tm + 1, tr));
}

void update(bool where, int pos, ll val, int v, int tl, int tr) {
    if (tl > pos || tr < pos)
        return;
    if (tl == tr) {
        mn[where][v] = min(mn[where][v], val);
        return;
    }
    int tm = (tl + tr) >> 1;
    update(where, pos, val, v << 1, tl, tm);
    update(where, pos, val, v << 1 | 1, tm + 1, tr);
    mn[where][v] = min(mn[where][v << 1], mn[where][v << 1 | 1]);
}

void build(bool where, int v, int tl, int tr) {
    if (tl == tr) {
        mn[where][v] = INF;
        return;
    }
    int tm = (tl + tr) >> 1;
    build(where, v << 1, tl, tm);
    build(where, v << 1 | 1, tm + 1, tr);
    mn[where][v] = INF;
}

void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        cin >> l[i] >> r[i] >> c[i] >> d[i];

    vector <int> als;
    als.push_back(1);
    als.push_back(m);
    for (int i = 0; i < n; i++) {
        als.push_back(l[i]);
        als.push_back(r[i]);
        als.push_back(c[i]);
    }

    sort(all(als));
    als.resize(unique(all(als)) - als.begin());

    int sz = (int)als.size();
    map <int, int> comp;
    for (int i = 0; i < sz; i++)
        comp[als[i]] = i;

    build(0, 1, 0, sz - 1);
    build(1, 1, 0, sz - 1);

    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ll lx = INF, rx = INF;
        if (l[i] == 1) lx = 0;
        else lx = min(lx, get_min(0, comp[l[i]], comp[r[i]], 1, 0, sz - 1));
        if (r[i] == m) rx = 0;
        else rx = min(rx, get_min(1, comp[l[i]], comp[r[i]], 1, 0, sz - 1));

        ans = min(ans, lx + rx + d[i]);

        if (l[i] == 1)
            update(0, comp[c[i]], 1ll * d[i], 1, 0, sz - 1);
        else
            update(0, comp[c[i]], get_min(0, comp[l[i]], comp[r[i]], 1, 0, sz - 1) + d[i], 1, 0, sz - 1);

        if (r[i] == m)
            update(1, comp[c[i]], 1ll * d[i], 1, 0, sz - 1);
        else
            update(1, comp[c[i]], get_min(1, comp[l[i]], comp[r[i]], 1, 0, sz - 1) + d[i], 1, 0, sz - 1);
    }

    if (ans >= INF)
        ans = -1;

    cout << ans << '\n';
}

main() {
    boost;
    solve();
    return 0;
}

Compilation message (stderr)

pinball.cpp:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main() {
      | ^~~~

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