oj.uz

Submission #107926

# Submission time Handle Problem Language Result Execution time Memory
107926 2019-04-26T09:22:30 Z someone_aa Pinball (JOI14_pinball) C++17
51 / 100
 1000 ms 12024 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 15 ms 384 KB Output is correct
19 Correct 10 ms 896 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 7 ms 896 KB Output is correct
23 Correct 6 ms 896 KB Output is correct
24 Correct 9 ms 896 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 15 ms 384 KB Output is correct
19 Correct 10 ms 896 KB Output is correct
20 Correct 7 ms 640 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 7 ms 896 KB Output is correct
23 Correct 6 ms 896 KB Output is correct
24 Correct 9 ms 896 KB Output is correct
25 Correct 249 ms 4180 KB Output is correct
26 Execution timed out 1072 ms 12024 KB Time limit exceeded
27 Halted 0 ms 0 KB -