Submission #1181342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181342		AlgorithmWarrior	Pinball (JOI14_pinball)	C++20	100 / 100	360 ms	35052 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

int const MAX=100005;
long long const INF=1000000000000000000;
int m,n;
int st[MAX],dr[MAX],loc[MAX],pret[MAX];
long long ans;

struct node{
    long long pref,suf;
    node(){
        pref=INF;
        suf=INF;
    }
};

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

struct segment_tree{
    node v[12*MAX];
    node combine(node a,node b){
        node comb;
        comb.pref=min(a.pref,b.pref);
        comb.suf=min(a.suf,b.suf);
        return comb;
    }
    void update(int nod,int st,int dr,int poz,node upd){
        if(st==dr)
            v[nod]=combine(v[nod],upd);
        else{
            int mij=(st+dr)/2;
            if(poz<=mij)
                update(2*nod,st,mij,poz,upd);
            else
                update(2*nod+1,mij+1,dr,poz,upd);
            v[nod]=combine(v[2*nod],v[2*nod+1]);
        }
    }
    node query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod];
        int mij=(st+dr)/2;
        node rasp;
        if(a<=mij)
            rasp=combine(rasp,query(2*nod,st,mij,a,b));
        if(b>mij)
            rasp=combine(rasp,query(2*nod+1,mij+1,dr,a,b));
        return rasp;
    }
}aint;

void read(){
    cin>>m>>n;
    int i;
    for(i=1;i<=m;++i)
        cin>>st[i]>>dr[i]>>loc[i]>>pret[i];
}

void normalize(){
    map<int,int>mep;
    mep[1]=0;
    mep[n]=0;
    int i;
    for(i=1;i<=m;++i){
        mep[st[i]]=0;
        mep[dr[i]]=0;
        mep[loc[i]]=0;
    }
    int id=0;
    for(auto &[val,valnou] : mep)
        valnou=++id;
    n=mep[n];
    for(i=1;i<=m;++i){
        st[i]=mep[st[i]];
        dr[i]=mep[dr[i]];
        loc[i]=mep[loc[i]];
    }
}

void get_dp(){
    ans=INF;
    int i;
    for(i=1;i<=m;++i){
        auto [cpref,csuf]=aint.query(1,1,n,st[i],dr[i]);
        if(st[i]==1)
            cpref=0;
        if(dr[i]==n)
            csuf=0;
        cpref+=pret[i];
        csuf+=pret[i];
        minself(cpref,INF);
        minself(csuf,INF);
        minself(ans,cpref+csuf-pret[i]);
        node upd;
        upd.pref=cpref;
        upd.suf=csuf;
        aint.update(1,1,n,loc[i],upd);
    }
}

void write(){
    if(ans<INF)
        cout<<ans;
    else
        cout<<-1;
}

int main()
{
    read();
    normalize();
    get_dp();
    write();
    return 0;
}

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