Submission #859334

#	Time	Username	Problem	Language	Result	Execution time	Memory
859334		sleepntsheep	Pinball (JOI14_pinball)	C++17	0 / 100	0 ms	344 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 (t[p+=n]=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;

    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);

        if (a[i].a == 0) tl.set(a[i].c, a[i].d);
        ll A = (a[i].a == 0) ? 0 : tl.qry(a[i].a, a[i].b);
        tl.set(a[i].c, A + a[i].d);

        A = (a[i].b == n - 1) ? 0 : tr.qry(a[i].a, a[i].b);
        tr.set(a[i].c, A + a[i].d);
        
        if (a[i].a == 0 && a[i].b == n - 1) z = min(z, a[i].d);
    }



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

    return 0;
}

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