Submission #859350

#	Time	Username	Problem	Language	Result	Execution time	Memory
859350		vjudge1	Pinball (JOI14_pinball)	C++17	100 / 100	154 ms	14384 KiB

pinball

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 200005
#define ALL(x) x.begin(), x.end()

int m, n;
struct pinball { ll a, b, c, d; } a[N];

int compress()
{
    vector<ll> crd = {1,n};
    for (int i = 1; i <= m; ++i) crd.push_back(a[i].a), crd.push_back(a[i].b), crd.push_back(a[i].c);
    sort(ALL(crd));
    crd.erase(unique(ALL(crd)), crd.end());
    for (int i = 1; i <= m; ++i) a[i].a = lower_bound(ALL(crd), a[i].a) - crd.begin(),
        a[i].b = lower_bound(ALL(crd), a[i].b) - crd.begin(),
        a[i].c = lower_bound(ALL(crd), a[i].c) - crd.begin();
    return crd.size();
}

struct min_segtree
{
    vector<ll> t;
    min_segtree(int n) : t(n<<1, 1e18) {};
    ll qry(int l, int r)
    {
        ll z = 1e18;
        for (l += n, r += n + 1; l < r; l/=2,r/=2)
        {
            if(l&1)z=min(z,t[l++]);
            if(r&1)z=min(t[--r],z);
        }
        return z;
    }
    void set(int p, ll k) { for (p+=n,t[p]=min(t[p],k);p/=2;)t[p]=min(t[p*2], t[p*2+1]); }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
    n = compress();

    min_segtree tl(n), tr(n);

    ll z = 1e18;

    tl.set(0, 0);
    tr.set(n-1, 0);

    for (int i = 1; i <= m; ++i)
    {
        z = min(z, tl.qry(a[i].a, a[i].b) + tr.qry(a[i].a, a[i].b) + a[i].d);
        tl.set(a[i].c, tl.qry(a[i].a, a[i].b) + a[i].d);
        tr.set(a[i].c, tr.qry(a[i].a, a[i].b) + a[i].d);
    }

    cout << (z < 1e18? z:-1);

    return 0;
}

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