Submission #247437

#	Time	Username	Problem	Language	Result	Execution time	Memory
247437		receed	Pinball (JOI14_pinball)	C++14	100 / 100	250 ms	17260 KiB

pinball

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 18;
ll tr[2][N * 2], inf = 1e16, a[N], b[N], c[N], d[N];

void add(int q, int p, ll x) {
    for (int i = N + p; i; i >>= 1)
        tr[q][i] = min(tr[q][i], x);
}

ll getm(int q, int cl, int cr, int v=1, int l=0, int r=N) {
    if (cr <= l || r <= cl)
        return inf;
    if (cl <= l && r <= cr)
        return tr[q][v];
    return min(getm(q, cl, cr, v * 2, l, (l + r) / 2), getm(q, cl, cr, v * 2 + 1, (l + r) / 2, r));
}

ll lb(vector<ll> &a, ll x) {
    return lower_bound(all(a), x) - a.begin();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll m, n;
    cin >> m >> n;
    vector<ll> li {2, n};
    rep(i, m) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        li.push_back(a[i]);
        li.push_back(b[i] + 1);
    }
    sort(all(li));
    li.resize(unique(all(li)) - li.begin());
    if (li[0] != 1 || li.back() != n + 1) {
        cout << -1;
        return 0;
    }
    rep(i, N * 2)
        rep(j, 2)
            tr[j][i] = inf;
    add(0, 0, 0);
    add(1, li.size() - 2, 0);
    ll ans = inf;
    rep(i, m) {
        a[i] = lb(li, a[i]);
        b[i] = lb(li, b[i] + 1);
        c[i] = lb(li, c[i] + 1) - 1;
        ll m1 = getm(0, a[i], b[i]), m2 = getm(1, a[i], b[i]);
        ans = min(ans, m1 + m2 + d[i]);
        add(0, c[i], m1 + d[i]);
        add(1, c[i], m2 + d[i]);
    }
    if (ans == inf)
        ans = -1;
    cout << ans;
}

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