Submission #1251497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251497		tvgk	Pinball (JOI14_pinball)	C++20	100 / 100	85 ms	7728 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;
const ll inf = 1e18 + 7;

int n, hole[mxN], nCol;
ll lt[mxN * 4], rt[mxN * 4], cost[mxN];
ii a[mxN];
vector<int> nen;

void Build(int j = 1, int l = 0, int r = nen.size() - 1)
{
    if (l == r)
    {
        lt[j] = inf;
        rt[j] = inf;

        if (!l)
            lt[j] = 0;
        if (l == nen.size() - 1)
            rt[j] = 0;
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    lt[j] = min(lt[j * 2], lt[j * 2 + 1]);
    rt[j] = min(rt[j * 2], rt[j * 2 + 1]);
}

ll GetL(int val, int j = 1, int l = 0, int r = nen.size() - 1)
{
    if (nen[r] < val)
        return inf;

    if (val <= nen[l])
        return lt[j];

    int mid = (l + r) / 2;
    return min(GetL(val, j * 2, l, mid), GetL(val, j * 2 + 1, mid + 1, r));
}

ll GetR(int val, int j = 1, int l = 0, int r = nen.size() - 1)
{
    if (val < nen[l])
        return inf;

    if (nen[r] <= val)
        return rt[j];

    int mid = (l + r) / 2;
    return min(GetR(val, j * 2, l, mid), GetR(val, j * 2 + 1, mid + 1, r));
}

void Upd(int vt, ll u, ll v, int j = 1, int l = 0, int r = nen.size() - 1)
{
    if (nen[l] > vt || vt > nen[r])
        return;

    lt[j] = min(lt[j], u);
    rt[j] = min(rt[j], v);
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Upd(vt, u, v, j * 2, l, mid);
    Upd(vt, u, v, j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> nCol;
    nen.push_back(1);
    nen.push_back(nCol);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se >> hole[i] >> cost[i];
        nen.push_back(hole[i]);
    }
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    Build();

    ll ans = inf;
    for (int i = 1; i <= n; i++)
    {
        ll u = GetL(a[i].fi);
        ll v = GetR(a[i].se);

        ans = min(ans, u + v + cost[i]);
        Upd(hole[i], u + cost[i], v + cost[i]);
    }

    if (ans == inf)
        cout << -1;
    else
        cout << ans;
}

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