Submission #1026858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026858		hotboy2703	Sky Walking (IOI19_walk)	C++17	100 / 100	882 ms	183148 KiB

walk

#include "walk.h"
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
struct walk{
    ll l,r,y;
};
vector <walk> all;
const ll MAXN = 1e5 + 100;
const ll INF = 1e18;
vector <pll> g[MAXN*20];
ll dist[MAXN*20];
ll dijkstra(ll s,ll t){
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;
    priority_queue <pll,vector <pll> ,greater <> > q;
    q.push(MP(dist[s],s));
    while (!q.empty()){
        auto u = q.top().se;
        ll val = q.top().fi;
        q.pop();
        if (dist[u] != val)continue;
        for (auto tmp:g[u]){
            ll v = tmp.fi,w = tmp.se;
            if (dist[u] + w < dist[v]){
                dist[v] = dist[u] + w;
                q.push(MP(dist[v],v));
            }
        }
    }
    if (dist[t] >=INF)dist[t] = -1;
    return dist[t];
}
ll SUSSYBAKA;
struct point{
    ll x,y,id;
    point(ll x1=-1,ll y1=-1):x(x1),y(y1),id(x1==-1?-1:SUSSYBAKA++){
    }
    bool operator < (const point &p)const {
        return MP(x,y)<MP(p.x,p.y);
    }
    bool operator == (const point &p)const {
        return MP(x,y)==MP(p.x,p.y);
    }
};
vector <point> vertices;
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){
    ll m = sz(l);
    ll n = sz(X);
    for (ll i = 0;i < m;i ++){
        all.push_back({l[i],r[i],y[i]});
    }
    sort(all.begin(),all.end(),[](walk a1,walk a2){return a1.y<a2.y;});
    vector <ll> order;
    order.resize(n);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](ll x,ll y){return h[x] > h[y];});
    vertices.emplace_back(X[S],0);
    vertices.emplace_back(X[G],0);
    for (auto x:all){
        vertices.emplace_back(X[x.l],x.y);
        vertices.emplace_back(X[x.r],x.y);
    }
    auto add_vertex = [&](bool inv){
        vector <ll> bd;
        for (ll i = inv?n-1:0;inv?i>=0:i<n;inv?i--:i++){
//            cout<<i<<endl;
            if (sz(bd) && h[bd.back()] < h[i])bd.pop_back();
            bd.push_back(i);
            if (i==S||i==G){
                ll ptr = sz(bd)-1;
                for (auto x:all){
                    while (ptr>=0&&h[bd[ptr]] < x.y)ptr--;
                    if (ptr != -1 && x.l <= bd[ptr] && bd[ptr] <= x.r){
                        vertices.emplace_back(X[bd[ptr]],x.y);
                    }
                }
            }
        }
    };
    add_vertex(0);
    add_vertex(1);
//    return -1;
    vector <pair <pll,bool> > event;
    for (auto x:all){
        event.emplace_back(MP(X[x.l],x.y),1);
        event.emplace_back(MP(X[x.r]+1,x.y),0);
    }
    sort(event.begin(),event.end());
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());

    {
        ll ptr = 0;
        multiset <ll> ms;
        vector <pll> Tm;
        for (auto x:vertices){
            while (ptr<sz(event) && event[ptr].fi.fi <= x.x){
                if (event[ptr].se)ms.insert(event[ptr].fi.se);
                else ms.erase(ms.find((event[ptr].fi.se)));
                ptr++;
            }
            auto tmp = ms.upper_bound(x.y);
            if (tmp != ms.end() && (*tmp) <= h[lower_bound(X.begin(),X.end(),x.x)-X.begin()])Tm.emplace_back(x.x,*(tmp));
            tmp = ms.lower_bound(x.y);
            if (tmp != ms.begin() && (*tmp) <= h[lower_bound(X.begin(),X.end(),x.x)-X.begin()])Tm.emplace_back(x.x,*prev(tmp));
        }
        for (auto x:Tm)vertices.emplace_back(x.fi,x.se);
    }
    sort(vertices.begin(),vertices.end());
    vertices.resize(unique(vertices.begin(),vertices.end())-vertices.begin());
    auto add_edge = [&](point a1,point a2){
        ll w = abs(a1.x-a2.x) + abs(a1.y-a2.y);
//        cout<<a1.x<<' '<<a1.y<<' '<<a2.x<<' '<<a2.y<<'\n';
        g[a1.id].push_back(MP(a2.id,w));
        g[a2.id].push_back(MP(a1.id,w));
    };
//    for (auto x:vertices){
//        cout<<x.x<<' '<<x.y<<' '<<x.id<<'\n';
//    }
    for (ll j = 0;j + 1 < sz(vertices);j ++){
        if (vertices[j].x == vertices[j+1].x)add_edge(vertices[j],vertices[j+1]);
    }
    auto cmp_y = [](point a1,point a2){return MP(a1.y,a1.x) < MP(a2.y,a2.x);};
    sort(vertices.begin(),vertices.end(),cmp_y);
    auto fi = [&](pll x){
        return lower_bound(vertices.begin(),vertices.end(),x,
                           [](point a1,pll val){return MP(a1.y,a1.x) < MP(val.se,val.fi);})-vertices.begin();
    };
    vector <ll> cnt(sz(vertices));
    for (auto x:all){
        cnt[fi(MP(X[x.l],x.y))] ++;
        cnt[fi(MP(X[x.r],x.y))] --;
    }
    for (ll i = 0;i < sz(vertices);i ++){
        if (i)cnt[i]+=cnt[i-1];
        if (cnt[i]){
            add_edge(vertices[i],vertices[i+1]);
        }
    }
    for (ll i = 0;i < sz(vertices);i ++){
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[S]),0LL))S = vertices[i].id;
        if (MP(vertices[i].x,vertices[i].y) == MP(ll(X[G]),0LL))G = vertices[i].id;

    }
    return dijkstra(S,G);
}

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