Submission #468437

#	Time	Username	Problem	Language	Result	Execution time	Memory
468437		stefantaga	Pinball (JOI14_pinball)	C++14	100 / 100	219 ms	19120 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef tuple<ll, ll, ll, ll> tpl;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 2;
const ll INF = 1e18;
ll n, m, k, ans;
ll A[MXN], B[MXN], C[MXN], D[MXN];
vector<ll> Num;
inline int GetId(ll x){
    return lower_bound(Num.begin(), Num.end(), x) - Num.begin() + 1;
}
struct Segtree {
    ll seg[MXS], lim;//lim as size
    void init(){
        lim = k + 1;
        for(int i = lim << 1; -- i; ) seg[i] = INF;
    }
    void Upd(ll p, ll x){
        p += lim;
        while(p) seg[p] = min(seg[p], x), p >>= 1;
    }
    ll Get(ll l, ll r){
        ll res = INF; l += lim, r += lim;
        while(l <= r){
            if((l & 1) == 1) res = min(res, seg[l]), l ++;
            if((r & 1) == 0) res = min(res, seg[r]), r --;
            l >>= 1, r >>= 1;
        }
        return res;
    }
} SL, SR;
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m, ans = INF;
    for(int i = 1; i <= n; i ++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        Num.push_back(A[i]), Num.push_back(B[i]), Num.push_back(C[i]);
    }
    Num.push_back(1), Num.push_back(m);
    sort(Num.begin(), Num.end());
    Num.resize(k = unique(Num.begin(), Num.end()) - Num.begin());
    SL.init(), SR.init();
    SL.Upd(1, 0), SR.Upd(k, 0);
    for(int i = 1; i <= n; i ++){
        A[i] = GetId(A[i]), B[i] = GetId(B[i]), C[i] = GetId(C[i]);
        ll cl = SL.Get(A[i], B[i]), cr = SR.Get(A[i], B[i]);
        ans = min(ans, cl + cr + D[i]);
        cl += D[i], cr += D[i];
        SL.Upd(C[i], cl), SR.Upd(C[i], cr);
    }
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}

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