Submission #1047948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047948		boyliguanhan	Sky Walking (IOI19_walk)	C++17	100 / 100	1473 ms	201696 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
map<int,int>pos[100100];
vector<pair<int,int>> adj[1<<20];
int CC;
void AE(int a,int b,int c){
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
}
int whatpos(int i,int j){
    if(pos[i].count(j))
        return pos[i][j];
    pos[i][j]=++CC;
    auto it=pos[i].find(j);
    if(it!=pos[i].begin())
        AE(prev(it)->second,CC,it->first-prev(it)->first);
    if(next(it)!=pos[i].end())
        AE(next(it)->second,CC,next(it)->first-it->first);
    return CC;
}
long long dis[1<<20];
long long djik(int a,int b){
    memset(dis,9,sizeof dis);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq;
    pq.push({0,a});
    dis[a]=0;
    while(pq.size()){
        auto[d,x]=pq.top();
        pq.pop();
        if(d-dis[x])continue;
        for(auto[v,w]:adj[x])
            if(dis[v]>d+w)
                pq.push({dis[v]=d+w,v});
    }
    return dis[b]<dis[0]?dis[b]:-1;
}
set<int>intersection[1<<20];
map<int,int>lft,rt;
void makestuf(VI h,int pos){
    lft.clear();
    rt.clear();
    int n=h.size();
    for(int i=0;i<=pos;i++) {
        lft[h[i]]=i;
        while(lft.begin()->first<h[i])
            lft.erase(lft.begin());
    }
    for(int i=n;i-->pos;){
        rt[h[i]]=i;
        while(rt.begin()->first<h[i])
            rt.erase(rt.begin());
    }
}
long long min_distance(VI x,VI h,VI l,VI r,VI y,int s,int g) {
    int m=l.size();
    makestuf(h,s);
    for(int i=0;i<m;i++)
        if(l[i]<s&&r[i]>s) {
            int A=lft.lower_bound(y[i])->second;
            int B=rt.lower_bound(y[i])->second;
            assert(A>=l[i]);
            assert(B<=r[i]);
            if(A-l[i])
                l.push_back(l[i]),
                r.push_back(l[i]=A),
                y.push_back(y[i]);
            if(B-r[i])
                r.push_back(r[i]),
                l.push_back(r[i]=B),
                y.push_back(y[i]);
        }
    m=l.size();
    makestuf(h,g);
    for(int i=0;i<m;i++)
        if(l[i]<g&&r[i]>g) {
            int A=lft.lower_bound(y[i])->second;
            int B=rt.lower_bound(y[i])->second;
            assert(A>=l[i]);
            assert(B<=r[i]);
            if(A-l[i])
                l.push_back(l[i]),
                r.push_back(l[i]=A),
                y.push_back(y[i]);
            if(B-r[i])
                r.push_back(r[i]),
                l.push_back(r[i]=B),
                y.push_back(y[i]);
        }
    m=l.size();
    vector<pair<int,int>> endpts;
    for(int i=0;i<m;i++) if(l[i]-r[i])
        endpts.push_back({l[i],i}),
        endpts.push_back({r[i],i}),
        whatpos(l[i],y[i]),whatpos(r[i],y[i]);
    sort(endpts.begin(),endpts.end());
    set<pair<int,int>> active;
    for(auto[b,i]:endpts){
        int pos=y[i];
        if(active.lower_bound({pos,0})!=active.begin()){
            auto it=--active.lower_bound({pos,0});
            intersection[it->second].insert(b);
            whatpos(b,it->first);
        }
        if(active.count({pos,i}))
            active.erase({pos,i});
        else active.insert({pos,i});
    }
    for(int i=0;i<m;i++){
        if(l[i]==r[i])continue;
        intersection[i].erase(l[i]);
        intersection[i].insert(r[i]);
        int prvind=whatpos(l[i],y[i]),prvpos=x[l[i]];
        for(auto j:intersection[i])
            AE(prvind,whatpos(j,y[i]),x[j]-prvpos),
            prvind=whatpos(j,y[i]),prvpos=x[j];
    }
    return djik(whatpos(s,0),whatpos(g,0));
}

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