Submission #1130172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130172		ngokhanh	Pinball (JOI14_pinball)	C++20	100 / 100	327 ms	41664 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define rep2(i,a,b,c) for (int i=a;i<=b;i+=c)
#define rev(i,a,b) for (int i=a;i>=b;i--)
#define rev2(i,a,b,c) for (int i=a;i>=b;i-=c)
#define pii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second
#define sz(a) (ll)(a.size())
#define on(n) __builtin_popcountll(n)
#define ld long double
#define __log2(x) 31-__builtin_clz(x)
#define Mask(x) (1LL<<x)
#define ALL(v) v.begin(),v.end()

const int N=1e5+5;
const int mod=1e9+9;
const int base=113;
const ll INF=1e15;
const int M=3e5;
const int M2=4*M+5;
ll m,n,A[N],B[N],C[N],D[N];
ll dp[N][2][2];
vector<int> v;

void compress(){
    v.pb(1),v.pb(n);
    rep(i,1,m) v.pb(A[i]),v.pb(B[i]),v.pb(C[i]);
    sort(ALL(v));
    v.resize(unique(ALL(v))-v.begin());
    rep(i,1,m){
        A[i]=lower_bound(ALL(v),A[i])-v.begin()+1;
        B[i]=lower_bound(ALL(v),B[i])-v.begin()+1;
        C[i]=lower_bound(ALL(v),C[i])-v.begin()+1;
    }
    n=lower_bound(ALL(v),n)-v.begin()+1;
}

struct IT{

    ll st[M2];

    void reset(int x,int l,int r){
        st[x]=INF;
        if (l==r) return;
        int m=(l+r)/2;
        reset(x*2,l,m);
        reset(x*2+1,m+1,r);
    }

    void update(int x,int l,int r,int pos,ll val){
        if (pos<l||r<pos||l>r) return;
        if (l==r){
            st[x]=min(st[x],val);
            return;
        }
        int m=(l+r)/2;
        update(x*2,l,m,pos,val);
        update(x*2+1,m+1,r,pos,val);
        st[x]=min(st[x*2],st[x*2+1]);
    }

    ll get(int x,int l,int r,int u,int v){
        if (v<l||r<u||l>r) return INF;
        if (u<=l&&r<=v) return st[x];
        int m=(l+r)/2;
        return min(get(x*2,l,m,u,v),get(x*2+1,m+1,r,u,v));
    }

    void Init() { reset(1,1,M);};

    void Upd(int u,ll v) { update(1,1,M,u,v); };

    ll Get(int l,int r) { return get(1,1,M,l,r); };
};

IT seg[2][2];

void solution(){
    cin >> m >> n;
    rep(i,1,m) cin >> A[i] >> B[i] >> C[i] >> D[i];
    rep(i,1,m)
        rep(j,0,1)
            rep(k,0,1) dp[i][j][k]=INF;
    rep(k,0,1)
        rep(t,0,1) seg[k][t].Init();
    compress();
    rep(i,1,m) dp[i][A[i]==1][B[i]==n]=D[i];
    rep(i,1,m){
        if (A[i]!=1&&B[i]!=n){
            rep(k,0,1)
                rep(t,0,1) dp[i][k][t]=min(dp[i][k][t],seg[k][t].Get(A[i],B[i])+D[i]);
        }
        if (A[i]==1&&B[i]!=n){
            rep(k,0,1) dp[i][1][0]=min(dp[i][1][0],seg[k][0].Get(A[i],B[i])+D[i]);
            rep(k,0,1) dp[i][1][1]=min(dp[i][1][1],seg[k][1].Get(A[i],B[i])+D[i]);
        }
        if (A[i]!=1&&B[i]==n){
            rep(k,0,1) dp[i][0][1]=min(dp[i][0][1],seg[0][k].Get(A[i],B[i])+D[i]);
            rep(k,0,1) dp[i][1][1]=min(dp[i][1][1],seg[1][k].Get(A[i],B[i])+D[i]);
        }
        if (A[i]==1&&B[i]==n){
            rep(k,0,1)
                rep(t,0,1) dp[i][1][1]=min(dp[i][1][1],seg[k][t].Get(A[i],B[i])+D[i]);
        }
        dp[i][1][1]=min(dp[i][1][1],dp[i][0][1]+dp[i][1][0]-D[i]);
        rep(k,0,1)
            rep(t,0,1) seg[k][t].Upd(C[i],dp[i][k][t]);
    }
    ll res=INF;
    rep(i,1,m) res=min(res,dp[i][1][1]);
    if (res==INF) res=-1;
    cout << res;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int test=1;
    //cin >> test;
    while(test--)
        solution();
}

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