제출 #602263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602263		leaked	Sky Walking (IOI19_walk)	C++17	25 / 100	924 ms	98484 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

const int N=1e5+1;
const ll inf=1e18;

map<int,ll> dp[N];
int y[N];

struct setik{
    map<pii,ll> dp;

    void upd(pii i,ll x){
        dp[i]=x;
        auto it=dp.lower_bound(i);
        if(it!=dp.begin() && prev(it)->s>dp[i])
            upd(prev(it)->f,x);
    }
    void getval(pii i,int yt){
//        cout<<"W "<<i.f<<' '<<i.s<<endl;
        dp[i]=inf;
        auto it=dp.lower_bound(i);
        ll vl=inf;
        if(next(it)!=dp.end() && y[next(it)->f.s]<=yt)
            umin(vl,next(it)->s);
        if(it!=dp.begin()){
//            cout<<prev(it)->f.s<<' '<<i.
            umin(vl,2*abs(y[prev(it)->f.s]-y[i.s])+prev(it)->s);
        }
        upd(i,vl);
    }
}_dp;
vec<pii> scan[N];
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){

    set<int> st;
    int n=sz(x);
    int m=sz(l);
    {
        vec<int> p(m);
        for(int i=0;i<m;i++) p[i]=i;
        sort(all(p),[&](int i,int j){return y[i]<y[j];});
        vec<int> nl(m),nr(m),ny(m);
        for(int i=0;i<m;i++)
            nl[i]=l[p[i]],nr[i]=r[p[i]],ny[i]=y[p[i]];
        swap(l,nl);swap(r,nr);swap(y,ny);
//        for(auto &z : y)
//            cout<<z<<' ';
//        cout<<endl;
    }
//    y.pb(0);
//    l.pb(n),r.pb(-1);

    {
        vec<array<int,3>> haha;
        st.insert(-1);
        st.insert(n);
        for(int i=0;i<n;i++) haha.pb({h[i],1,i});
        for(int i=0;i<m;i++) haha.pb({y[i],0,i});
        sort(rall(haha));
        for(auto &z : haha){
            if(z[1]==0){
                l[z[2]]=*st.lower_bound(l[z[2]]);
                r[z[2]]=*prev(st.upper_bound(r[z[2]]));
            }
            else{
                st.insert(z[2]);
            }
        }
        st.clear();
    }
    for(int i=0;i<m;i++){
        if(l[i]>r[i]) continue;
        scan[l[i]].pb({i,1});
        scan[r[i]+1].pb({i,-1});
        ::y[i]=y[i];
    }
    if(s==0 && g==n-1){
        for(auto &z : scan[0]){
            _dp.upd(m_p(y[z.f],z.f),2*y[z.f]);
        }
        for(int i=1;i<n;i++){
            for(auto &z : scan[i]){
                if(z.s==-1){
//                    cout<<"DEL "<<z.f<endl;
                    _dp.dp.erase(m_p(y[z.f],z.f));
                }
            }
            auto it=_dp.dp.upper_bound(m_p(h[i-1],1e9));
            if(it!=_dp.dp.end() && it->f.f<=h[i]){
                auto itj=_dp.dp.upper_bound(m_p(h[i],-1));
                --itj;
                if(itj->s!=inf){
                    while(it->s==inf) ++it;
                    _dp.upd(it->f,it->s);
                }
            }
            for(auto &z : scan[i]){
                if(z.s==-1) continue;
                _dp.getval(m_p(y[z.f],z.f),h[i]);
            }
//            cout<<i<<endl;
//            for(auto &q : _dp.dp)
//                cout<<q.f<<' '<<q.s<<endl;
//            cout<<endl;
        }
        ll mn=inf;
        for(auto &z : _dp.dp)
            umin(mn,z.s+x[n-1]-x[0]);
        if(mn==inf)
            mn=-1;
        return mn;
    }

    vec<vec<int>> ids(m,vec<int>());
    for(int i=0;i<n;i++){
        dp[i][-1]=inf;
        for(auto &z : scan[i]){
            if(z.s==-1)
                st.erase(z.f);
            else
                st.insert(z.f);
        }
        for(auto z : st){
            if(y[z]>h[i]) break;
//            cout<<"I "<<i<<' '<<z<<endl;
            dp[i][z]=inf;
            ids[z].pb(i);
        }
    }

    priority_queue<array<ll,3>,vec<array<ll,3>>,greater<array<ll,3>>> pq;
    pq.push({0,s,-1});
    dp[s][-1]=0;
    while(!pq.empty()){
        auto [xt,v,j]=pq.top();pq.pop();
        if(dp[v][j]!=xt) continue;
//        cout<<v<<' '<<j<<' '<<dp[v][j]<<endl;
        auto getnxt=[&](int v,int j){
            if(j==-1)
                return n;
            int w=lower_bound(all(ids[j]),v)-ids[j].begin();
            if(w==sz(ids[j])-1)
                return n;
            return ids[j][w+1];
        };
        auto getprv=[&](int v,int j){
            if(j==-1)
                return -1;
            int w=lower_bound(all(ids[j]),v)-ids[j].begin();
            if(w==0)
                return -1;
            return ids[j][w-1];
        };

        int f=getnxt(v,j),s=getprv(v,j);

        for(auto &z : {f,s}){
            if(z==n || z==-1)
                continue;
            if(umin(dp[z][j],xt+abs(x[z]-x[v])))
                pq.push({dp[z][j],z,j});
        }
//        assert(dp[v].count(j));
        auto it=dp[v].find(j);
//        cout<<next(it)->f<<endl;
        if(next(it)!=dp[v].end()){
            int nj=next(it)->f;
            int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
            if(umin(dp[v][nj],xt+r))
                pq.push({dp[v][nj],v,nj});
        }
        if(it!=dp[v].begin()){
            int nj=prev(it)->f;
            int r=abs((nj==-1?0:y[nj])-(j==-1?0:y[j]));
            if(umin(dp[v][nj],xt+r))
                pq.push({dp[v][nj],v,nj});
        }
    }
    if(dp[g][-1]==inf)
        dp[g][-1]=-1;
    return dp[g][-1];
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43