Submission #887153

#	Time	Username	Problem	Language	Result	Execution time	Memory
887153		maxFedorchuk	Pinball (JOI14_pinball)	C++14	100 / 100	489 ms	46164 KiB

pinball

#include<bits/stdc++.h>
using namespace std;

const long long MX=3e5+10;
const long long INF=1e18;

long long mas[2][4*MX];

void build(long long v,long long tl,long long tr)
{
    mas[0][v]=INF;
    mas[1][v]=INF;

    if(tl==tr)
    {
        return;
    }

    long long mid=(tl+tr)/2;

    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);

    return;
}

long long get_mn(long long in,long long v,long long tl,long long tr,long long l,long long r)
{
    if(l<=tl && tr<=r)
    {
        return mas[in][v];
    }

    if(tr<l || r<tl)
    {
        return INF;
    }

    long long mid=(tl+tr)/2;
    return min(get_mn(in,v*2,tl,mid,l,r),get_mn(in,v*2+1,mid+1,tr,l,r));
}

void upd(long long in,long long v,long long tl,long long tr,long long pos,long long zn)
{
    if(tl==tr)
    {
        mas[in][v]=min(mas[in][v],zn);
        return;
    }

    long long mid=(tl+tr)/2;

    if(pos<=mid)
    {
        upd(in,v*2,tl,mid,pos,zn);
    }
    else
    {
        upd(in,v*2+1,mid+1,tr,pos,zn);
    }

    mas[in][v]=min(mas[in][v*2],mas[in][v*2+1]);

    return;
}

long long m,n;

pair < pair < long long , long long > , pair < long long , long long > > zap[MX];

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

    map < long long , long long > mp;

    cin>>m>>n;

    for(long long i=1;i<=m;i++)
    {
        cin>>zap[i].first.first>>zap[i].first.second>>zap[i].second.first>>zap[i].second.second;

        mp[zap[i].first.first]=1;
        mp[zap[i].first.second]=1;
        mp[zap[i].second.first]=1;
    }
    mp[1]=1;
    mp[n]=1;

    long long uk=0;
    for(auto & u:mp)
    {
        uk++;
        u.second=uk;
    }
    n=uk;

    build(1,1,n);
    upd(0,1,1,n,1,0);
    upd(1,1,1,n,n,0);

    long long res=INF;
    for(long long i=1;i<=m;i++)
    {
        zap[i].first.first=mp[zap[i].first.first];
        zap[i].first.second=mp[zap[i].first.second];
        zap[i].second.first=mp[zap[i].second.first];

        res=min(res,get_mn(0,1,1,n,zap[i].first.first,zap[i].first.second)+get_mn(1,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second);

        upd(0,1,1,n,zap[i].second.first,get_mn(0,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second);
        upd(1,1,1,n,zap[i].second.first,get_mn(1,1,1,n,zap[i].first.first,zap[i].first.second)+zap[i].second.second);
    }

    if(res==INF)
    {
        res=-1;
    }

    cout<<res<<"\n";
    return 0;
}

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