Submission #504118

#	Time	Username	Problem	Language	Result	Execution time	Memory
504118		colossal_pepe	Pinball (JOI14_pinball)	C++17	100 / 100	220 ms	17552 KiB

pinball

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int MAXN = 100005;

int n, m, a[MAXN], b[MAXN], c[MAXN];
ll d[MAXN];
vector<ll> v;
vector<vector<ll>> dp;

void compress() {
    set<ll> s;
    for (int i = 0; i < n; i++) {
        if (s.find(c[i]) != s.end()) continue;
        s.insert(c[i]);
        v.push_back(c[i]);
    }
    sort(v.begin(), v.end());
}

ll query(int tree, int node, int l, int r, int L, int R) {
    if (r < L or l >= R) return INF;
    int mid = (l + r) / 2;
    if (L <= l and r < R) return dp[tree][node];
    else return min(query(tree, 2 * node, l, mid, L, R), query(tree, (2 * node) + 1, mid + 1, r, L, R));
}

void update(int tree, int node, int l, int r, int pos, ll x) {
    if (l == r) dp[tree][node] = min(dp[tree][node], x);
    else {
        int mid = (l + r) / 2;
        if (pos > mid) update(tree, (2 * node) + 1, mid + 1, r, pos, x);
        else update(tree, 2 * node, l, mid, pos, x);
        dp[tree][node] = min(dp[tree][2 * node], dp[tree][(2 * node) + 1]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    compress();
    int sz = v.size();
    dp.resize(2, vector<ll>(4 * sz, INF));
    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ll ansl = INF, ansr = INF;
        if (a[i] == 1) ansl = d[i];
        if (b[i] == m) ansr = d[i];
        int l = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        int r = upper_bound(v.begin(), v.end(), b[i]) - v.begin();
        ansl = min(ansl, query(0, 1, 0, sz - 1, l, r) + d[i]);
        ansr = min(ansr, query(1, 1, 0, sz - 1, l, r) + d[i]);
        int pos = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
        if (ansl != INF and ansr != INF) ans = min(ans, ansl + ansr - d[i]);
        update(0, 1, 0, sz - 1, pos, ansl);
        update(1, 1, 0, sz - 1, pos, ansr);
    }
    cout << (ans != INF ? ans : -1) << '\n';
    return 0;
}

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