Submission #869874

#	Time	Username	Problem	Language	Result	Execution time	Memory
869874		12345678	Pinball (JOI14_pinball)	C++17	100 / 100	418 ms	177260 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5, inf=1e9;
ll dpl[nx], dpr[nx], n, m, a[nx], b[nx], c[nx], d[nx], ml, mr, res=1e17;

struct segtree
{
    struct node
    {
        ll val;
        node *l, *r;
        node(): val(1e17), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt=0;
    void update(int l, int r, pnode &i, int idx, ll val)
    {
        if (!i) i=new node();
        if (r<idx||idx<l) return;
        if (l==r) return void(i->val=min(val, i->val));
        int md=(l+r)/2;
        update(l, md, i->l, idx, val);
        update(md+1, r, i->r, idx, val);
        i->val=min(i->l->val, i->r->val);
    }
    ll query(int l, int r, pnode i, int ql, int qr)
    {
        if (qr<l||r<ql||!i) return 1e17;
        if (ql<=l&&r<=qr) return i->val;
        int md=(l+r)/2;
        return min(query(l, md, i->l, ql, qr), query(md+1, r, i->r, ql, qr));
    }
} sl, sr;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>m>>n;
    for (int i=1; i<=m; i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
    for (int i=1; i<=m; i++)
    {
        dpl[i]=dpr[i]=ml=mr=1e17;
        if (a[i]==1) dpl[i]=d[i], ml=0;
        if (b[i]==n) dpr[i]=d[i], mr=0;
        ll resl=sl.query(1, n, sl.rt, a[i], b[i]);
        ll resr=sr.query(1, n, sr.rt, a[i], b[i]);
        dpl[i]=min(dpl[i], resl+d[i]);
        dpr[i]=min(dpr[i], resr+d[i]);
        sl.update(1, n, sl.rt, c[i], dpl[i]);
        sr.update(1, n, sr.rt, c[i], dpr[i]);
        ml=min(ml, resl);
        mr=min(mr, resr);
        res=min(res, ml+mr+d[i]);
        //cout<<i<<' '<<dpl[i]<<' '<<dpr[i]<<' '<<ml<<' '<<mr<<' '<<res<<'\n';
    }
    cout<<((res==1e17)?-1:res);
}

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