Submission #330333

#	Time	Username	Problem	Language	Result	Execution time	Memory
330333		gevacrt	Pinball (JOI14_pinball)	C++17	100 / 100	689 ms	172672 KiB

pinball

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF 1000000000000000
#define MOD 1000000007
#define all(x) x.begin(), x.end()

class SegTree{
    struct nda{
        int v = INF;
        nda *l = NULL, *r = NULL;
    } *st;
    
    int l, r;
    void Update(nda *node, int l, int r, int L, int R, int val){
        if(r < L or R < l) return;
        if(L <= l and r <= R){
            node->v = min(node->v, val);
            return;
        }

        if(node->l == NULL) node->l = new nda;
        if(node->r == NULL) node->r = new nda;

        int m = (l+r)>>1;
        Update(node->l, l, m, L, R, val);
        Update(node->r, m+1, r, L, R, val);
        node->v = min((node->l)->v,(node->r)->v);
        return;
    }

    int Query(nda *node, int l, int r, int L, int R){
        if(r < L or R < l) return INF;
        if(L <= l and r <= R) return node->v;
        int m = (l+r)>>1;
        int v1 = INF, v2 = INF;
        
        if(node->l != NULL) v1 = Query(node->l, l, m, L, R);
        if(node->r != NULL) v2 = Query(node->r, m+1, r, L, R);

        return min(v1,v2);
    }

    public:
        SegTree(int l, int r){
            st = new nda;
            this->l = l, this->r = r;
        }

        void Update(int L, int R, int val){
            Update(st, l, r, L, R, val);
            return;
        }

        int Query(int L, int R){
            return Query(st, l, r, L, R);
        }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n; cin >> m >> n;
    SegTree SL(1, n), SR(1, n);
    SL.Update(1,1,0); SR.Update(n,n,0);
    
    int ans = 5*INF;
    while(m--){
        int l, r, c, d; cin >> l >> r >> c >> d;

        int k1 = SL.Query(l, r), k2 = SR.Query(l, r);
        if(k1 < INF && k2 < INF) ans = min(ans, k1+d+k2);

        SL.Update(c,c,k1+d); SR.Update(c,c,k2+d);
    }

    if(ans == 5*INF) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

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