Submission #623212

#	Time	Username	Problem	Language	Result	Execution time	Memory
623212		wiwiho	Sky Walking (IOI19_walk)	C++14	0 / 100	4120 ms	691016 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct bridge{
    int l, r, y;
    int lid = -1, rid = -1;
};

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int from, int to){

    int n = X.size();
    int m = L.size();
    if(from > to) swap(from, to);

    vector<vector<int>> sp(m);
    for(int i = 0; i < m; i++){
        sp[i].eb(L[i]);
        sp[i].eb(R[i]);
    }

    vector<vector<int>> lp(n + 1), rp(n + 1);
    for(int i = 0; i < m; i++){
        lp[L[i]].eb(i);
        rp[R[i]].eb(i);
    }

    /*{
        vector<int> v;
        set<int> now;
        for(int i = 0; i < n; i++){
            while(!v.empty() && H[v.back()] <= H[i]) v.pob;
            v.eb(i);
            for(int j : lp[i]) now.insert(j);
            if(i == from || i == to){
                for(int j : now){
                    int y = Y[j];
                    auto it = lower_bound(iter(v), y, [&](int e, int val){ return val <= H[e]; } );
                    it--;
                    int pos = *it;
                    sp[j].eb(pos);
                }
            }
            for(int j : rp[i]) now.erase(j);
        }
    }

    {
        vector<int> v;
        set<int> now;
        for(int i = n - 1; i >= 0; i--){
            while(!v.empty() && H[v.back()] <= H[i]) v.pob;
            v.eb(i);
            for(int j : rp[i]) now.insert(j);
            if(i == from || i == to){
                for(int j : now){
                    int y = Y[j];
                    auto it = lower_bound(iter(v), y, [&](int e, int val){ return val <= H[e]; } );
                    it--;
                    int pos = *it;
                    sp[j].eb(pos);
                }
            }
            for(int j : lp[i]) now.erase(j);
        }
    }*/

    vector<bridge> bri;
    for(int i = 0; i < m; i++){
        lsort(sp[i]);
        uni(sp[i]);
        //cerr << "bridge " << i << " : ";
        //printv(sp[i], cerr);
        //assert(sp[i].front() == L[i]); OK
        //assert(sp[i].back() == R[i]); OK
        for(int j = 0; j + 1 < (int)sp[i].size(); j++){
            bri.eb(bridge({sp[i][j], sp[i][j + 1], Y[i]}));
        }
    }

    fill(iter(lp), vector<int>());
    fill(iter(rp), vector<int>());

    for(auto i : bri){
        lp[i.l].eb(i.y);
        rp[i.r].eb(i.y);
    }
    
    vector<pii> ps;
    /*{
        multiset<int> now;
        for(int i = 0; i < n; i++){
            for(int j : lp[i]) now.insert(j);

            auto add = [&](int y){
                //cerr << "add " << X[i] << " " << y << "\n";
                ps.eb(mp(X[i], y));
                auto it = now.upper_bound(y);
                if(it != now.end() && *it <= H[i]) ps.eb(mp(X[i], *it));
                it = now.lower_bound(y);
                if(it != now.begin()) ps.eb(mp(X[i], *prev(it)));
            };

            for(int j : lp[i]) add(j);
            for(int j : rp[i]) add(j);

            for(int j : rp[i]) now.erase(now.find(j));
        }
    }*/
    for(auto i : bri){
        for(int j = i.l; j <= i.r; j++){
            if(H[j] < i.y) continue;
            ps.eb(mp(X[j], i.y));
        }
    }

    ps.eb(mp(X[from], 0));
    ps.eb(mp(X[to], 0));
    lsort(ps);
    uni(ps);
    //printv(ps, cerr);

    auto getid = [&](int x, int y){
        return lower_bound(iter(ps), mp(x, y)) - ps.begin();
    };

    int sid = getid(X[from], 0);
    int gid = getid(X[to], 0);
    for(auto& i : bri){
        i.lid = getid(X[i.l], i.y);
        i.rid = getid(X[i.r], i.y);
    }

    int sz = ps.size();
    vector<vector<pll>> g(sz);
    auto addedge = [&](int u, int v){
        ll w = abs(ps[u].F - ps[v].F) + abs(ps[u].S - ps[v].S);
        //cerr << "addedge " << u << " " << ps[u] << " " << v << " " << ps[v] << " " << w << "\n";
        g[u].eb(mp(v, w));
        g[v].eb(mp(u, w));
    };

    for(int i = 0; i + 1 < sz; i++){
        if(ps[i].F == ps[i + 1].F){
            addedge(i, i + 1);
        }
    }
    
    vector<int> tmp(sz);
    iota(iter(tmp), 0);
    auto comp = [&](int a, int b){ return mp(ps[a].S, ps[a].F) < mp(ps[b].S, ps[b].F); };
    sort(iter(tmp), comp);

    for(auto i : bri){
        int pos = lower_bound(iter(tmp), i.lid, comp) - tmp.begin();
        while(tmp[pos] != i.rid){
            int now = tmp[pos], nxt = tmp[pos + 1];
            addedge(now, nxt);
            pos++;
        }
    }

    vector<ll> dis(sz, 1LL << 60);
    std::priority_queue<pll, vector<pll>, greater<>> pq;
    pq.push(mp(0, sid));
    dis[sid] = 0;
    while(!pq.empty()){
        int now = pq.top().S;
        ll d = pq.top().F;
        pq.pop();
        if(d != dis[now]) continue;
        
        for(pll i : g[now]){
            if(dis[i.F] <= d + i.S) continue;
            dis[i.F] = d + i.S;
            pq.push(mp(d + i.S, i.F));
        }
    }

	return dis[gid];
}

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