Submission #591900

#	Time	Username	Problem	Language	Result	Execution time	Memory
591900		Hanksburger	Pinball (JOI14_pinball)	C++17	100 / 100	69 ms	9324 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
map<long long, long long> dpl;
map<long long, long long, greater<long long> > dpr;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, ans=1e18;
    cin >> n >> m;
    dpl[1]=dpr[m]=0;
    dpl[m]=dpr[1]=1e18;
    for (long long i=1; i<=n; i++)
    {
        long long a, b, c, d, l, r;
        cin >> a >> b >> c >> d;
        l=dpl.lower_bound(a)->second;
        r=dpr.lower_bound(b)->second;
        ans=min(ans, l+r+d);
        auto it=dpl.insert({c, l+d}).first;
        long long k=min(it->second, l+d);
        it->second=k;
        if (next(it)!=dpl.end() && next(it)->second<=k)
            it=dpl.erase(it);
        while (it!=dpl.begin() && (--it)->second>=k)
            it=dpl.erase(it);
        it=dpr.insert({c, r+d}).first;
        k=min(it->second, r+d);
        it->second=k;
        if (next(it)!=dpr.end() && next(it)->second<=k)
            it=dpr.erase(it);
        while (it!=dpr.begin() && (--it)->second>=k)
            it=dpr.erase(it);
    }
    if (ans<=1e17)
        cout << ans;
    else
        cout << -1;
    return 0;
}

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