Submission #84143

#	Time	Username	Problem	Language	Result	Execution time	Memory
84143		Bodo171	Pinball (JOI14_pinball)	C++14	100 / 100	691 ms	76316 KiB

pinball

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <fstream>
using namespace std;
const int nmax=100005;
const long long lim=1LL*1e16;
vector<int> all;
map<int,int> norm;
long long cost[nmax];
long long ans,x,y;
int st[nmax],dr[nmax],out[nmax];
int n,m,i,nr;
struct aint
{
    long long arb[12*nmax];
    void init(int nr)
    {
        for(int i=1;i<=4*nr;i++)
            arb[i]=lim;
    }
    void update(int nod,int l,int r,int poz,long long val)
    {
        arb[nod]=min(arb[nod],val);
        if(l==r)
            return;
        int m=(l+r)/2;
        if(poz<=m) update(2*nod,l,m,poz,val);
        else update(2*nod+1,m+1,r,poz,val);
    }
    long long query(int nod,int l,int r,int st,int dr)
    {
        if(st<=l&&r<=dr)
          return arb[nod];
        int m=(l+r)/2;
        long long ret=lim;
        if(st<=m) ret=min(ret,query(2*nod,l,m,st,dr));
        if(m<dr) ret=min(ret,query(2*nod+1,m+1,r,st,dr));
        return ret;
    }
}leftt,rightt;
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>st[i]>>dr[i]>>out[i]>>cost[i];
        all.push_back(st[i]);
        all.push_back(dr[i]);
        all.push_back(out[i]);
    }
    all.push_back(1);all.push_back(m);
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    nr=all.size();
    for(i=0;i<nr;i++)
       norm[all[i]]=i+1;
    leftt.init(nr);rightt.init(nr);
    leftt.update(1,1,nr,1,0);
    rightt.update(1,1,nr,nr,0);
    ans=lim;
    for(i=1;i<=n;i++)
    {
        st[i]=norm[st[i]];dr[i]=norm[dr[i]];
        out[i]=norm[out[i]];
        x=leftt.query(1,1,nr,st[i],dr[i]);
        y=rightt.query(1,1,nr,st[i],dr[i]);
        if(x+y+cost[i]<ans)
            ans=1LL*x+y+cost[i];
        leftt.update(1,1,nr,out[i],x+cost[i]);
        rightt.update(1,1,nr,out[i],y+cost[i]);
    }
    if(ans==lim) ans=-1;
    cout<<ans;
    return 0;
}

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