Submission #656734

#	Time	Username	Problem	Language	Result	Execution time	Memory
656734		socpite	Pinball (JOI14_pinball)	C++14	100 / 100	259 ms	21988 KiB

pinball

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

#define f first
#define s second

typedef long long ll;

const int maxn = 3e5+5;
const ll inf = 1e18;

vector<int> pos;
ll st[2][4*maxn];

int pp(int x){
    return lower_bound(pos.begin(), pos.end(), x)-pos.begin();
}

int A[maxn], B[maxn], C[maxn], D[maxn];

int n, m, sz;

void upd(int ty, int l, int r, int k, ll val, int id){
    if(l==r)st[ty][id] = min(st[ty][id], val);
    else{
        int mid = (l+r)>>1;
        if(k <= mid)upd(ty, l, mid, k, val, id<<1);
        else upd(ty, mid+1, r, k, val, id<<1|1);
        st[ty][id] = min(st[ty][id<<1], st[ty][id<<1|1]);
    }
}

ll query(int ty, int l, int r, int ql, int qr, int id){
    if(l > qr || ql > r)return inf;
    if(ql <= l && qr >= r)return st[ty][id];
    else{
        int mid = (l+r)>>1;
        return min(query(ty, l, mid, ql, qr, id<<1), query(ty, mid+1, r, ql, qr, id<<1|1));
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ll ans = inf;
    pos = {-1, 1, m};
    for(int i = 0; i < n; i++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        pos.push_back(A[i]);
        pos.push_back(B[i]);
        pos.push_back(C[i]);
    }
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    sz = pos.size()-1;
    for(int i = 0; i < 4*maxn; i++)st[0][i]=st[1][i]=inf;
    upd(0, 1, sz, 1, 0, 1);
    upd(1, 1, sz, sz, 0, 1);
    for(int i = 0; i < n; i++){
        A[i] = pp(A[i]);
        B[i] = pp(B[i]);
        C[i] = pp(C[i]);
        ll lt = query(0, 1, sz, A[i], B[i], 1), rt = query(1, 1, sz, A[i], B[i], 1);
        ans = min(ans, D[i] + lt + rt);
        upd(0, 1, sz, C[i], lt+D[i], 1);
        upd(1, 1, sz, C[i], rt+D[i], 1);
    }
    if(ans >= inf)cout << "-1";
    else cout << ans;
}
                

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