Submission #609744

#	Time	Username	Problem	Language	Result	Execution time	Memory
609744		leaked	Sky Walking (IOI19_walk)	C++17	100 / 100	1959 ms	370880 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;
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);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;

const int N=1e5+1;


struct segtree{
    int t[4*N];
    void build(int v,int tl,int tr,vec<int> &a){
        if(tl==tr){
            t[v]=a[tl];
        }
        else{
            int tm=(tl+tr)>>1;
            build(2*v,tl,tm,a);build(2*v+1,tm+1,tr,a);
            t[v]=max(t[v<<1],t[v<<1|1]);
        }
    }

    int findf(int l,int r,int x,int v,int tl,int tr){
        if(tl>r||tr<l||t[v]<x)
            return -1;
        if(tl==tr)
            return tl;
        int tm=(tl+tr)>>1;
        int j=findf(l,r,x,2*v,tl,tm);
        if(j==-1) j=findf(l,r,x,2*v+1,tm+1,tr);
        return j;
    }
    int findl(int l,int r,int x,int v,int tl,int tr){
        if(tl>r||tr<l||t[v]<x)
            return -1;
        if(tl==tr)
            return tl;
        int tm=(tl+tr)>>1;
        int j=findl(l,r,x,2*v+1,tm+1,tr);
        if(j==-1) j=findl(l,r,x,2*v,tl,tm);
        return j;
    }
}sega;


int n;

vec<array<int,3>> process(vec<array<int,3>> arr,int p){

    vec<array<int,3>> wi;

    for(auto &z : arr){
        auto [l,r,h] = z;
        int l1=l,r1=r;

        l=sega.findf(l,r,h,1,0,n-1);
        r=sega.findl(l,r,h,1,0,n-1);

        if(l==-1) l=r1+1;
        if(r==-1) r=l1-1;

        if(l>r) continue;

        if(l<=p && r>=p){
            int a=sega.findl(l,p,h,1,0,n-1);
            int b=sega.findf(p,r,h,1,0,n-1);
            assert(a!=-1 && b!=-1);

            wi.pb({l,a,h});
            wi.pb({a,b,h});
            wi.pb({b,r,h});

        }
        else{
            wi.pb({l,r,h});
        }
    }

    return wi;
}

const int NT=2e6+1;

vec<pii> g[2*NT];

map<int,int> cords[N];
set<pii> pos[NT];

int tt=0;
int getid(int i,int j){
//    cout<<"I "<<i<<' '<<j<<endl;
    if(!cords[i].count(j)){
        cords[i][j]=tt++;
        pos[j].insert({i,cords[i][j]});
    }
    return cords[i][j];
}
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 gt){

    n=sz(x);
    sega.build(1,0,n-1,h);

    vec<array<int,3>> arr;
    int m=sz(l);
    for(int i=0;i<m;i++) arr.pb({l[i],r[i],y[i]});


    arr=process(arr,s);
    arr=process(arr,gt);

    sort(all(arr));
    arr.erase(unique(all(arr)),arr.end());

    sort(all(arr),[&](array<int,3> f,array<int,3> s){
        return f[2]<s[2];
    });

////    for(auto &z : arr)
////        cout<<z[0]<<' '<<z[1]<<' '<<z[2]<<endl;
////    exit(0);

    m=sz(arr);

    vec<vec<int>> adds(n,vec<int>());
    vec<vec<int>> dels(n,vec<int>());

    for(int i=0;i<m;i++){
        adds[arr[i][0]].pb(i);
        dels[arr[i][1]].pb(i);
    }

    set<int> st;

    for(int i=0;i<n;i++){


        for(auto &z : adds[i]){
            auto it=st.lower_bound(z);
            getid(i,z);

            if(it!=st.begin()){
                int c=*prev(it);

                getid(i,c);


                int v=getid(i,c),u=getid(i,z),w=abs(arr[c][2]-arr[z][2]);
                g[v].pb({u,w});
                g[u].pb({v,w});
            }
        }

        for(auto &z : adds[i]){
            st.insert(z);
        }

        for(auto &z : dels[i]){
            st.erase(z);
        }


        for(auto &z : dels[i]){
            auto it=st.lower_bound(z);
            getid(i,z);

            if(it!=st.begin()){
                int c=*prev(it);
                getid(i,c);
            }
        }



    }

    int fi=tt++,si=tt++;

    for(auto &z : cords[s]){
        g[fi].pb({z.s,arr[z.f][2]});
    }
    for(auto &z : cords[gt]){
//        cout<<"SHIS "<<z.s<<' '<<arr[z.f][2]<<endl;
        g[z.s].pb({si,arr[z.f][2]});
    }

    for(int i=0;i<m;i++){
        pii last=m_p(-1,-1);
        for(auto z : pos[i]){
            if(last.f!=-1){
                int v=last.s,u=z.s,w=abs(x[z.f]-x[last.f]);


                g[v].pb({u,w});
                g[u].pb({v,w});

            }
            last=z;
        }
    }

    for(int i=0;i<n;i++){
        pii last=m_p(-1,-1);
        for(auto &z : cords[i]){
            if(last.f!=-1){
                int v=last.s,u=z.s,w=abs(arr[z.f][2]-arr[last.f][2]);

                g[v].pb({u,w});
                g[u].pb({v,w});
            }
            last=z;
        }
    }

    const ll inf=1e18;

    vec<ll> dst(tt,inf);

    priority_queue<pli,vec<pli>,greater<pli>> pq;

    dst[fi]=0;
    pq.push({dst[fi],fi});

    while(!pq.empty()){
        auto [d,v]=pq.top();pq.pop();
//        cout<<"PQ "<<d<<' '<<v<<endl;
        if(dst[v]!=d) continue;
        for(auto &z : g[v]){
            if(umin(dst[z.f],d+z.s)){
                pq.push({dst[z.f],z.f});
            }
        }
    }

    if(dst[si]==inf) dst[si]=-1;

    return dst[si];
}

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