Submission #1319506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319506		wangzhiyi33	Pinball (JOI14_pinball)	C++20	100 / 100	264 ms	24692 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=5e5;

struct seg{
    int l,r,val;
    seg *lf,*rg;
 
    void build(int x,int y){
        l=x,r=y;
        if(l==r){
            val=1e18;
            return;
        }
        int mid=(l+r)/2;
        lf=new seg();
        rg=new seg();
        lf->build(l,mid); rg->build(mid+1,r);
        val=min(lf->val,rg->val);
    }
 
    void update(int idx,int v){
        if(l==r){
            val=min(val,v);
            return;
        }
        int mid=(l+r)/2;
        if(idx<=lf->r)lf->update(idx,v);
        else rg->update(idx,v);
        val=min(lf->val,rg->val);
    }
 
    int query(int posl,int posr){
        if(l>posr || r<posl)return 1e18;
        if(l>=posl && r<=posr)return val;
        //int mid=(l+r)/2;
        int satu=lf->query(posl,posr);
        int dua=rg->query(posl,posr);
        return min(satu,dua);
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;
    int a[n+1],b[n+1],c[n+1],d[n+1];
    for(int q=1;q<=n;q++){
        cin>>a[q]>>b[q]>>c[q]>>d[q];
    }

    vector<int>comp;
    for(int q=1;q<=n;q++){
        comp.pb(c[q]);
    }
    comp.push_back(1),comp.push_back(m);
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());

    seg isi;
    isi.build(1,comp.size());
    isi.update(1,0);
    int lf[n+1],rg[n+1];
    
    int ans=1e18;
    for(int q=1;q<=n;q++){
        lf[q]=1e18;
        int idr=upper_bound(comp.begin(),comp.end(),b[q])-comp.begin()-1;
        int idl=lower_bound(comp.begin(),comp.end(),a[q])-comp.begin();
        idr++,idl++;
        int brp=isi.query(idl,idr);
        lf[q]=brp+d[q];

        int id=lower_bound(comp.begin(),comp.end(),c[q])-comp.begin();
        id++;
        isi.update(id,lf[q]);
    }

    isi.build(1,comp.size());
    isi.update(comp.size(),0);
    for(int q=1;q<=n;q++){
        rg[q]=1e18;
        int idr=upper_bound(comp.begin(),comp.end(),b[q])-comp.begin()-1;
        int idl=lower_bound(comp.begin(),comp.end(),a[q])-comp.begin();
        idr++,idl++;
        int brp=isi.query(idl,idr);
        rg[q]=brp+d[q];

        int id=lower_bound(comp.begin(),comp.end(),c[q])-comp.begin();
        id++;
        isi.update(id,rg[q]);
       // cout<<rg[q]<<"K"<<q<<endl;
        ans=min(ans,lf[q]+rg[q]-d[q]);
    }
    if(ans==1e18)ans=-1;
    cout<<ans<<endl;
    
}

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