Submission #107940

#	Time	Username	Problem	Language	Result	Execution time	Memory
107940		someone_aa	Pinball (JOI14_pinball)	C++17	100 / 100	667 ms	95516 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];

class node {
public:
    P value = mp(inf, inf);
    ll lbound, rbound;
    node *lchild, *rchild;

    node(ll _lb, ll _rb) {
        lchild = rchild = NULL;
        lbound = _lb;
        rbound = _rb;
    }
    P lvalue() {
        if(lchild == NULL) return mp(inf, inf);
        else return lchild->value;
    }
    P rvalue() {
        if(rchild == NULL) return mp(inf, inf);
        else return rchild->value;
    }
    void update(int uind, bool type, ll val) {
        if(lbound == rbound) {
            if(type == 0) value.first = min(value.first, val);
            else value.second = min(value.second, val);
        }
        else {
            int mid = (lbound + rbound) / 2;

            if(uind <= mid) {
                if(lchild == NULL)
                    lchild = new node(lbound, mid);
                lchild -> update(uind, type, val);
            }
            else {
                if(rchild == NULL)
                    rchild = new node(mid+1, rbound);
                rchild -> update(uind, type, val);
            }

            P lval = lvalue();
            P rval = rvalue();

            value.first = min(lval.first, rval.first);
            value.second = min(lval.second, rval.second);
        }
    }
    P query(int ql, int qr) {
        if(lbound > qr || rbound < ql) return mp(inf, inf);
        else if(lbound >= ql && rbound <= qr) return value;
        else {
            P lval, rval;
            if(lchild == NULL) lval = mp(inf, inf);
            else lval = lchild -> query(ql, qr);

            if(rchild == NULL) rval = mp(inf, inf);
            else rval = rchild -> query(ql, qr);

            return mp(min(lval.first, rval.first), min(lval.second, rval.second));
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;

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

    node *root = new node(1, m);

    ll result = LLONG_MAX;
    for(int i=0;i<n;i++) {
        // O(N^2) algorithm
        /*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];
            root->update(c[i], 0, dpl[i]);
        }
        else {
            P X = root->query(a[i], b[i]);
            dpl[i] = X.first + d[i];
            //cout<<X.first<<"\n";
            root->update(c[i], 0, dpl[i]);
        }

        if(b[i] == m) {
            dpr[i] = d[i];
            root->update(c[i], 1, dpr[i]);
        }
        else {
            P X = root->query(a[i], b[i]);
            if(X.second == inf) dpr[i] = inf;
            else dpr[i] = X.second + d[i];
            root->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: 49 / 49