Submission #695209

#	Time	Username	Problem	Language	Result	Execution time	Memory
695209		four_specks	Pinball (JOI14_pinball)	C++17	100 / 100	78 ms	12512 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

void solve()
{
    int m, n;
    cin >> m >> n;

    vector<tuple<long, long, long, long>> v(m);
    for (auto &[a, b, c, d] : v)
        cin >> a >> b >> c >> d, --a, --b, --c;

    long cost = LONG_MAX;

    map<long, long> ft, bk;
    ft.emplace(0, 0);
    bk.emplace(n - 1, 0);
    for (auto [a, b, c, d] : v)
    {
        {
            auto it_ft = ft.lower_bound(a), it_bk = bk.upper_bound(b);
            if (it_ft != ft.end() && it_bk != bk.begin())
                cost = min(cost, it_ft->second + prev(it_bk)->second + d);
        }
        {
            auto it = ft.lower_bound(a);
            if (it != ft.end())
            {
                long x = it->second;

                it = ft.lower_bound(c);
                if (it == ft.end() || x + d < it->second)
                {
                    it = ft.upper_bound(c);
                    while (it != ft.begin() && prev(it)->second > x + d)
                        ft.erase(prev(it));
                    ft.emplace(c, x + d);
                }
            }
        }
        {
            auto it = bk.upper_bound(b);
            if (it != bk.begin())
            {
                long x = prev(it)->second;

                it = bk.upper_bound(c);
                if (it == bk.begin() || x + d < prev(it)->second)
                {
                    it = bk.lower_bound(c);
                    while (it != bk.end() && it->second > x + d)
                        it = bk.erase(it);
                    bk.emplace(c, x + d);
                }
            }
        }
    }

    cout << (cost != LONG_MAX ? cost : -1) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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