Submission #107926

#	Time	Username	Problem	Language	Result	Execution time	Memory
107926		someone_aa	Pinball (JOI14_pinball)	C++17	51 / 100	1072 ms	12024 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
using namespace std;
const int maxn = 100100;
const ll inf = (1LL<<50);
int n, m;
ll a[maxn], b[maxn],c[maxn], d[maxn], br;
set<ll>st;
map<ll,int>ind;
P tree[12*maxn];

ll dpl[maxn], dpr[maxn];

void update(int ind, bool type, ll value, int li=1, int ri=br, int index=1) {
    if(li == ri) {
        if(type == 0) tree[index].first = min(tree[index].first, value);
        else tree[index].second = min(tree[index].second, value);
    }
    else {
        int mid = (li + ri) / 2;
        if(ind <= mid) update(ind, type, value, li, mid, 2*index);
        else update(ind, type, value, mid+1, ri, 2*index+1);

        tree[index].first = min(tree[2*index].first, tree[2*index+1].first);
        tree[index].second = min(tree[2*index].second, tree[2*index+1].second);
    }
}

P query(int ql, int qr, int li=1, int ri=br, int index=1) {
    if(li > qr || ri < ql) return mp(inf, inf);
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li + ri) / 2;

        P lq = query(ql,qr,li,mid,2*index);
        P rq = query(ql,qr,mid+1,ri,2*index+1);
        return mp(min(lq.first, rq.first), min(lq.second, rq.second));
    }
}

int main() {
    cin>>n>>m;

    for(int i=0;i<n;i++) {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        st.insert(a[i]);
        st.insert(b[i]);
        st.insert(c[i]);
    }
    st.insert(m);

    br = 1;
    for(int i:st) {
        ind[i] = br++;
    }

    for(int i=1;i<=4*br;i++) tree[i].first = tree[i].second = inf;

    ll result = LLONG_MAX;
    for(int i=0;i<n;i++) {
        /*a[i] = ind[a[i]];
        b[i] = ind[b[i]];
        c[i] = ind[c[i]];*/

        dpl[i] = dpr[i] = inf;
        if(a[i] == 1) {
            dpl[i] = d[i];
        }
        if(b[i] == m) {
            dpr[i] = d[i];
        }

        for(int j=0;j<i;j++) {
            if(c[j] >= a[i] && c[j] <= b[i]) {
                dpl[i] = min(dpl[i], dpl[j] + d[i]);
                dpr[i] = min(dpr[i], dpr[j] + d[i]);
            }
        }

        // O(NlogN) algorithm, doesn't work
        //cout<<i<<":\n";
        /*if(a[i] == 1) {
            dpl[i] = d[i];
            update(c[i], 0, dpl[i]);
        }
        else {
            P X = query(a[i], b[i]);
            dpl[i] = X.first + d[i];
            //cout<<X.first<<"\n";
            update(c[i], 0, dpl[i]);
        }

        if(b[i] == ind[m]) {
            dpr[i] = d[i];
            update(c[i], 1, dpr[i]);
        }
        else {
            P X = query(a[i], b[i]);
            if(X.second == inf) dpr[i] = inf;
            else dpr[i] = X.second + d[i];
            update(c[i], 1, dpr[i]);
        }
        //cout<<dpl[i]<<" + "<<dpr[i]<<" - "<<d[i]<<"\n";*/
        result = min(result, dpl[i] + dpr[i] - d[i]);
    }
    if(result >= inf) {
        cout<<"-1\n";
    }
    else {
        cout<<result<<"\n";
    }

    return 0;
}

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