Submission #283323

#	Time	Username	Problem	Language	Result	Execution time	Memory
283323		Kastanda	Sky Walking (IOI19_walk)	C++14	100 / 100	1382 ms	157096 KiB

walk

// M
#include<bits/stdc++.h>
#include "walk.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100005, MXM = N * 5, MXN = MXM * 2;
int n, ts, A[N], MX[N * 4], Lid[MXM], Rid[MXM];
vector < int > S[N], E[N], V[N], ID[N];
vector < pair < int , ll > > Adj[MXN];
ll D[MXN];
inline void AddEdge(int v, int u, ll w)
{
        assert(w >= 0);
        Adj[v].pb({u, w});
        Adj[u].pb({v, w});
}
void Build(int id = 1, int l = 0, int r = n)
{
        if (r - l < 2)
                return void(MX[id] = A[l]);
        Build(lc, l, md);
        Build(rc, md, r);
        MX[id] = max(MX[lc], MX[rc]);
}
int GetFirst(int i, int val, int id = 1, int l = 0, int r = n)
{
        if (r <= i || MX[id] < val)
                return -1;
        if (r - l < 2)
                return l;
        int rt = GetFirst(i, val, lc, l, md);
        if (rt != -1)
                return rt;
        return GetFirst(i, val, rc, md, r);
}
int GetLast(int i, int val, int id = 1, int l = 0, int r = n)
{
        if (i < l || MX[id] < val)
                return -1;
        if (r - l < 2)
                return l;
        int rt = GetLast(i, val, rc, md, r);
        if (rt != -1)
                return rt;
        return GetLast(i, val, lc, l, md);
}
ll min_distance(vector < int > X, vector < int > H, vector < int > L, vector < int > R, vector < int > Y, int st, int fn)
{
        n = (int)X.size();
        for (int i = 0; i < n; i ++)
                A[i] = H[i];
        Build();

        if (st > fn)
                swap(st, fn);
        if (st == fn)
                return 0LL;

        for (int i = 0; i < (int)L.size(); i ++)
                if (L[i] < st && st < R[i])
                {
                        int l = GetLast(st, Y[i]);
                        int r = GetFirst(st, Y[i]);
                        assert(l != -1 && r != -1);
                        assert(l >= L[i] && r <= R[i]);
                        if (L[i] < l)
                                L.pb(L[i]), R.pb(l), Y.pb(Y[i]);
                        if (r < R[i])
                                L.pb(r), R.pb(R[i]), Y.pb(Y[i]);
                        L[i] = l; R[i] = r;
                }
        for (int i = 0; i < (int)L.size(); i ++)
                if (L[i] == R[i])
                {
                        swap(L[i], L.back()); L.pop_back();
                        swap(R[i], R.back()); R.pop_back();
                        swap(Y[i], Y.back()); Y.pop_back();
                        i --;
                }
        for (int i = 0; i < (int)L.size(); i ++)
                if (L[i] < fn && fn < R[i])
                {
                        int l = GetLast(fn, Y[i]);
                        int r = GetFirst(fn, Y[i]);
                        assert(l != -1 && r != -1);
                        assert(l >= L[i] && r <= R[i]);
                        if (L[i] < l)
                                L.pb(L[i]), R.pb(l), Y.pb(Y[i]);
                        if (r < R[i])
                                L.pb(r), R.pb(R[i]), Y.pb(Y[i]);
                        L[i] = l; R[i] = r;
                }
        for (int i = 0; i < (int)L.size(); i ++)
                if (L[i] == R[i])
                {
                        swap(L[i], L.back()); L.pop_back();
                        swap(R[i], R.back()); R.pop_back();
                        swap(Y[i], Y.back()); Y.pop_back();
                        i --;
                }
        for (int i = 0; i < (int)L.size(); i ++)
                S[L[i]].pb(i), E[R[i]].pb(i);
        for (int i = 0; i < n; i ++)
        {
                if (i == st || i == fn)
                        V[i].pb(0);
                for (int j : S[i])
                        V[i].pb(Y[j]);
                for (int j : E[i])
                        V[i].pb(Y[j]);
                sort(V[i].begin(), V[i].end());
                V[i].resize(unique(V[i].begin(), V[i].end()) - V[i].begin());
                for (int j : V[i])
                        ID[i].pb(ts ++);
        }
        for (int i = 0; i < (int)L.size(); i ++)
        {
                Lid[i] = ID[L[i]][(int)(lower_bound(V[L[i]].begin(), V[L[i]].end(), Y[i]) - V[L[i]].begin())];
                Rid[i] = ID[R[i]][(int)(lower_bound(V[R[i]].begin(), V[R[i]].end(), Y[i]) - V[R[i]].begin())];
        }

        set < pair < int , int > > ST;
        for (int i = 0; i < n; i ++)
        {
                for (int j : E[i])
                        ST.erase({Y[j], j});
                for (int j = 1; j < (int)V[i].size(); j ++)
                        AddEdge(ID[i][j - 1], ID[i][j], V[i][j] - V[i][j - 1]);
                for (int j = 0; j < (int)V[i].size(); j ++)
                {
                        auto it = ST.lower_bound({V[i][j], -1});
                        if (it != ST.begin())
                        {
                                it --;
                                assert(it->first < V[i][j]);
                                AddEdge(ts, ID[i][j], V[i][j] - it->first);
                                AddEdge(Lid[it->second], ts, X[i] - X[L[it->second]]);
                                Lid[it->second] = ts;
                                L[it->second] = i;
                                ts ++; it ++;
                        }
                        if (it != ST.end() && it->first <= H[i])
                        {
                                assert(it->first >= V[i][j]);
                                AddEdge(ts, ID[i][j], it->first - V[i][j]);
                                AddEdge(Lid[it->second], ts, X[i] - X[L[it->second]]);
                                Lid[it->second] = ts;
                                L[it->second] = i;
                                ts ++;
                        }
                }
                for (int j : S[i])
                        ST.insert({Y[j], j});
        }
        for (int i = 0; i < (int)L.size(); i ++)
                AddEdge(Lid[i], Rid[i], X[R[i]] - X[L[i]]);
        priority_queue < pair < ll , int > > Pq;
        memset(D, 63, sizeof(D));
        D[ID[st][0]] = 0;
        Pq.push({0, ID[st][0]});
        while (Pq.size())
        {
                ll d = -Pq.top().first;
                int v = Pq.top().second;
                Pq.pop();
                if (v == ID[fn][0])
                        return d;
                if (d > D[v])
                        continue;
                for (auto u : Adj[v])
                        if (D[u.first] > D[v] + u.second)
                                D[u.first] = D[v] + u.second, Pq.push({-D[u.first], u.first});
        }
        return -1LL;
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:117:26: warning: unused variable 'j' [-Wunused-variable]
  117 |                 for (int j : V[i])
      |                          ^

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