Submission #1013408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013408		boris_mihov	Sky Walking (IOI19_walk)	C++17	0 / 100	49 ms	58964 KiB

walk

#include "walk.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <map>
 
typedef long long llong;
const int MAXN = 100000 + 10;
const int INTERSECTIONS = 10 + 5;
const llong INF = 1e18;
const int INTINF = 1e9;
const int MAXLOG = 17;
 
namespace
{
    int cnt;
    int n, m;
    int s, t;
    int h[MAXN];
    int x[MAXN];
    int left[MAXN];
    int right[MAXN];
    int y[MAXN];
    std::map <int,int> map[MAXN];
    bool vis[MAXN * INTERSECTIONS];
    llong dist[MAXN * INTERSECTIONS];
    std::vector <std::pair <int,int>> g[MAXN * INTERSECTIONS]; 
    int cntNodes;
}
 
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    int getLOG[MAXN];
 
    void build(int a[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = a[i];
        }
 
        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int i = 1 ; i + (1 << lg) - 1 <= n ; ++i)
            {
                sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
            }
        }
 
        for (int i = 1 ; i <= n ; ++i)
        {
            getLOG[i] = getLOG[i - 1];
            if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
        }
    }
 
    int findMAX(int l, int r)
    {
        int lg = getLOG[r - l + 1];
        return std::max(sparse[lg][l], sparse[lg][r - (1 << lg) + 1]);
    }
};
 
Sparse sparse;
llong solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        map[i][0] = ++cnt;
    }
 
    sparse.build(h);
    for (int i = 1 ; i <= m ; ++i)
    {
        int prev = left[i];
        if (map[left[i]][y[i]] == 0)
        {
            map[left[i]][y[i]] = ++cnt;
        }
 
        while (prev < right[i])
        {
            int l = prev, r = right[i] + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                if (sparse.findMAX(prev + 1, mid) < y[i]) l = mid;
                else r = mid;
            }
 
            if (map[r][y[i]] == 0)
            {
                map[r][y[i]] = ++cnt;
            }
 
            // std::cout << "here: " << prev << ' ' << r << ' ' << y[i] << '\n';
            g[map[prev][y[i]]].push_back({map[r][y[i]], x[r] - x[prev]});
            g[map[r][y[i]]].push_back({map[prev][y[i]], x[r] - x[prev]});
            prev = r;
        }
    }
 
    for (int i = 1 ; i <= n ; ++i)
    {
        auto prev = map[i].begin();
        for (auto curr = std::next(map[i].begin()) ; curr != map[i].end() ; ++curr)
        {
            // std::cout << "edge ver: " << x[i] << ' ' << prev->first << ' ' << x[i] << ' ' << curr->first << '\n';
            g[prev->second].push_back({curr->second, curr->first - prev->first});
            g[curr->second].push_back({prev->second, curr->first - prev->first});
            prev = curr;
        }
    }
 
    std::priority_queue <std::pair <llong,int>> pq;
    std::fill(dist + 1, dist + 1 + cnt, INF);
    pq.push({0, map[s][0]});
    dist[map[s][0]] = 0;
 
    while (pq.size())
    {
        auto [d, node] = pq.top();
        pq.pop();
 
        if (vis[node])
        {
            continue;
        }
 
        vis[node] = true;
        for (const auto &[u, ed] : g[node])
        {
            if (dist[u] > dist[node] + ed)
            {
                dist[u] = dist[node] + ed;
                pq.push({-dist[u], u});
            }
        }
    }
 
	return (dist[map[t][0]] == INF ? -1 : dist[map[t][0]]);
}

struct Fenwick
{
    int tree[MAXN];
    void update(int idx, int val)
    {
        assert(idx != 0);
        for (; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int idx)
    {
        int res = 0;
        for (; idx ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int kth(int k)
    {
        int idx = 0;
        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (idx + (1 << lg) <= n && tree[idx + (1 << lg)] < k)
            {
                idx += (1 << lg);
                k -= tree[idx];
            }
        }

        return idx + 1;
    }
};

int lastX[MAXN];
int lastNode[MAXN];
int permY[MAXN];
int order[MAXN];
Fenwick fenwick;
std::vector <int> activate[MAXN];
std::vector <int> deactivate[MAXN];
int firstBigger[MAXN];

llong solveSpecial()
{
    map[1][0] = ++cnt; 
    map[n][0] = ++cnt; 
    std::iota(permY + 1, permY + 1 + m, 1);
    std::sort(permY + 1, permY + 1 + m, [&](int a, int b)
    {
        return y[a] < y[b];
    });

    for (int i = 1 ; i <= m ; ++i)
    {
        order[permY[i]] = i;
    }

    firstBigger[permY[m]] = m + 1;
    for (int i = m - 1 ; i >= 1 ; --i)
    {
        firstBigger[permY[i]] = firstBigger[permY[i + 1]];
        while (y[permY[firstBigger[permY[i]] - 1]] > y[permY[i]])
        {
            firstBigger[permY[i]]--;
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        activate[left[i]].push_back(i);
        deactivate[right[i] + 1].push_back(i);
    }
    
    for (int i = 1 ; i <= m ; ++i)
    {
        for (const int &idx : activate[i])
        {
            fenwick.update(order[idx], 1);
        }

        for (const int &idx : deactivate[i])
        {
            fenwick.update(order[idx], -1);
        }

        for (const int &idx : activate[i])
        {
            map[i][y[idx]] = ++cnt;
            lastNode[idx] = cnt;
            lastX[idx] = x[i];
        }

        for (const int &idx : activate[i])
        {
            int below = fenwick.query(order[idx] - 1);
            if (fenwick.query(firstBigger[idx] - 1) > fenwick.query(order[idx]))
            {
                below = fenwick.query(firstBigger[idx] - 1);
            }
            
            if (below)
            {
                int newIdx = permY[fenwick.kth(below)];
                if (lastX[newIdx] != x[i])
                {
                    map[i][y[newIdx]] = ++cnt;
                    g[lastNode[newIdx]].push_back({map[i][y[newIdx]], x[i] - lastX[newIdx]});
                    g[map[i][y[newIdx]]].push_back({lastNode[newIdx], x[i] - lastX[newIdx]});
                    lastX[newIdx] = x[i];
                    lastNode[newIdx] = map[i][y[newIdx]];
                }

                g[map[i][y[newIdx]]].push_back({map[i][y[idx]], y[idx] - y[newIdx]});
                g[map[i][y[idx]]].push_back({map[i][y[newIdx]], y[idx] - y[newIdx]});
            }
        }

        for (const int &idx : deactivate[i + 1])
        {
            if (lastX[idx] != x[i])
            {
                map[i][y[idx]] = ++cnt;
                g[lastNode[idx]].push_back({cnt, x[i] - lastX[idx]});
                g[cnt].push_back({lastNode[idx], x[i] - lastX[idx]});
                lastX[idx] = x[i];
                lastNode[idx] = cnt;
            }

            int below = fenwick.query(order[idx] - 1);
            if (fenwick.query(firstBigger[idx] - 1) > fenwick.query(order[idx]))
            {
                below = fenwick.query(firstBigger[idx] - 1);
            }
            
            if (below)
            {
                int newIdx = permY[fenwick.kth(below)];
                if (lastX[newIdx] != x[i])
                {
                    map[i][y[newIdx]] = ++cnt;
                    g[lastNode[newIdx]].push_back({cnt, x[i] - lastX[newIdx]});
                    g[cnt].push_back({lastNode[newIdx], x[i] - lastX[newIdx]});
                    lastX[newIdx] = x[i];
                    lastNode[newIdx] = cnt;
                }

                g[map[i][y[newIdx]]].push_back({map[i][y[idx]], y[idx] - y[newIdx]});
                g[map[i][y[idx]]].push_back({map[i][y[newIdx]], y[idx] - y[newIdx]});
            }
        }
    }
    
    if (map[1].size() > 1)
    {
        auto node = std::next(map[1].begin());
        g[map[1][0]].push_back({node->second, node->first});
        g[node->second].push_back({map[1][0], node->first});
    }

    if (map[n].size() > 1)
    {
        auto node = std::next(map[n].begin());
        g[map[n][0]].push_back({node->second, node->first});
        g[node->second].push_back({map[n][0], node->first});
    }

    std::priority_queue <std::pair <llong,int>> pq;
    std::fill(dist + 1, dist + 1 + cnt, INF);
    pq.push({0, map[s][0]});
    dist[map[s][0]] = 0;
 
    while (pq.size())
    {
        auto [d, node] = pq.top();
        pq.pop();

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, ed] : g[node])
        {
            if (dist[u] > dist[node] + ed)
            {
                dist[u] = dist[node] + ed;
                pq.push({-dist[u], u});
            }
        }
    }
 
	return (dist[map[t][0]] == INF ? -1 : dist[map[t][0]]);
}
 
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 t) 
{
    n = x.size();
    m = l.size();
    ::s = s + 1; ::t = t + 1;
 
    for (int i = 0 ; i < n ; ++i)
    {
        ::h[i + 1] = h[i];
        ::x[i + 1] = x[i];
    }
 
    std::vector <int> perm(m);
    std::iota(perm.begin(), perm.end(), 0);
    std::sort(perm.begin(), perm.end(), [&](int x, int y)
    {
        return l[x] < l[y];
    });
 
    for (int i = 0 ; i < m ; ++i)
    {
        ::left[i + 1] = l[perm[i]] + 1;
        ::right[i + 1] = r[perm[i]] + 1;
        ::y[i + 1] = y[perm[i]];
    }
 
    if (::s == 1 && ::t == n) return solveSpecial();
    return solve();
}

Compilation message (stderr)

walk.cpp: In member function 'void Sparse::build(int*)':
walk.cpp:51:89: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |                 sparse[lg][i] = std::max(sparse[lg - 1][i], sparse[lg - 1][i + (1 << lg - 1)]);
      |                                                                                      ~~~^~~
walk.cpp:58:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   58 |             if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
      |                       ~~~~~~~~~~^~~
walk.cpp: In function 'llong solve()':
walk.cpp:91:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |                 mid = l + r >> 1;
      |                       ~~^~~
walk.cpp: At global scope:
walk.cpp:32:9: warning: '{anonymous}::cntNodes' defined but not used [-Wunused-variable]
   32 |     int cntNodes;
      |         ^~~~~~~~

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