Submission #1251456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251456		khoavn2008	Pinball (JOI14_pinball)	C++20	100 / 100	173 ms	29340 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define REP(i,r) for(ll i=0,_r=(r);i<_r;i++)
#define FOR(i,l,r) for(ll i=(l),_r=(r);i<=_r;i++)
#define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define FORNG(i,r,l) for(ll i=(r),_l=(l);i>=_l;i--)
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1LL)
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())

const ll MOD = 1e9+7, N = 3e5+10, INF = 1e18, LOG = 20;
struct Seg{
    ll n;
    vector<ll> st;
    Seg(ll n = 0):n(n){
        st.assign(n * 4 + 100, INF);
    }
    void update(ll pos,ll val,ll id,ll l,ll r){
        if(r < pos || pos < l)return;
        if(l == r){
            st[id] = min(st[id], val);
            return;
        }
        ll mid = (l + r) >> 1;
        update(pos, val, id * 2, l, mid);
        update(pos, val, id * 2 + 1, mid + 1, r);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }
    ll getmin(ll u,ll v,ll id,ll l,ll r){
        if(r < u || v < l)return INF;
        if(u <= l && r <= v)return st[id];
        ll mid = (l + r) >> 1;
        return min(getmin(u, v, id * 2, l, mid), getmin(u, v, id * 2 + 1, mid + 1, r)); 
    }
    void update(ll u,ll v){update(u, v, 1, 1, n);}
    ll getmin(ll u,ll v){return getmin(u, v, 1, 1, n);}
}stL, stR;
ll n,m,maVal;
ll comL[N],comR[N],comD[N],c[N];

int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    vector<array<ll,3>> vec = {{-INF,-1,-1},{1,0,0},{m,0,0}};
    FOR(i,1,n){
        ll l,r,d;cin>>l>>r>>d>>c[i];
        vec.pb({l,i,0});
        vec.pb({r,i,1});
        vec.pb({d,i,2});
    }
    sort(all(vec));
    FOR(i,1,size(vec) - 1){
        if(vec[i][0] != vec[i - 1][0])maVal++;
        if(vec[i][2] == 0)comL[vec[i][1]] = maVal;
        if(vec[i][2] == 1)comR[vec[i][1]] = maVal;
        if(vec[i][2] == 2)comD[vec[i][1]] = maVal;
    }
    // cout<<maVal<<endl;
    stL = Seg(maVal);
    stR = Seg(maVal);
    ll ans = INF;
    FOR(i,1,n){
        ll L = comL[i],R = comR[i],D = comD[i],C = c[i];
        // cout<<L<<' '<<R<<' '<<D<<endl;
        if(L == 1 && R == maVal)ans = min(ans, C);
        else{
            if(L == 1){
                // cout<<"L"<<' '<<i<<endl;
                ans = min(ans, stR.getmin(L, R) + C);
                stL.update(D, C);
            }else if(R == maVal){
                // cout<<"R"<<' '<<i<<endl;
                ans = min(ans, stL.getmin(L, R) + C);
                stR.update(D, C);
            }else{
                // cout<<i<<endl;
                ans = min(ans, stL.getmin(L, R) + stR.getmin(L, R) + C);
                stL.update(D, stL.getmin(L, R) + C);
                stR.update(D, stR.getmin(L, R) + C);
            }
        }
    }
    cout<<(ans == INF ? -1 : ans);
}

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