oj.uz

Submission #1013397

# Submission time Handle Problem Language Result Execution time Memory
1013397 2024-07-03T13:54:13 Z boris_mihov Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 202064 KB 
#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)
    {
        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 + n, 1);
    std::sort(permY + 1, permY + 1 + n, [&](int a, int b)
    {
        return y[a] < y[b];
    });

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

    firstBigger[permY[n]] = n + 1;
    for (int i = n - 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 <= n ; ++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({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]});
            }
        }

        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

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51544 KB Output is correct
2 Correct 8 ms 51548 KB Output is correct
3 Correct 8 ms 49500 KB Output is correct
4 Correct 8 ms 49376 KB Output is correct
5 Correct 8 ms 53848 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct
7 Correct 10 ms 53852 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 10 ms 53852 KB Output is correct
10 Correct 8 ms 49500 KB Output is correct
11 Correct 8 ms 49500 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 8 ms 53592 KB Output is correct
14 Correct 8 ms 49500 KB Output is correct
15 Correct 9 ms 49364 KB Output is correct
16 Correct 8 ms 49496 KB Output is correct
17 Correct 8 ms 49496 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49500 KB Output is correct
2 Correct 8 ms 49500 KB Output is correct
3 Correct 511 ms 145384 KB Output is correct
4 Correct 343 ms 161872 KB Output is correct
5 Correct 209 ms 146868 KB Output is correct
6 Correct 179 ms 136436 KB Output is correct
7 Correct 204 ms 147024 KB Output is correct
8 Correct 676 ms 176048 KB Output is correct
9 Correct 265 ms 145492 KB Output is correct
10 Correct 586 ms 202064 KB Output is correct
11 Correct 211 ms 108392 KB Output is correct
12 Correct 109 ms 85588 KB Output is correct
13 Correct 196 ms 101156 KB Output is correct
14 Correct 92 ms 90964 KB Output is correct
15 Correct 94 ms 92096 KB Output is correct
16 Correct 116 ms 93264 KB Output is correct
17 Correct 89 ms 91216 KB Output is correct
18 Correct 322 ms 84992 KB Output is correct
19 Correct 12 ms 53520 KB Output is correct
20 Correct 52 ms 68436 KB Output is correct
21 Execution timed out 4033 ms 74832 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 56528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 56528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51544 KB Output is correct
2 Correct 8 ms 51548 KB Output is correct
3 Correct 8 ms 49500 KB Output is correct
4 Correct 8 ms 49376 KB Output is correct
5 Correct 8 ms 53848 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct
7 Correct 10 ms 53852 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 10 ms 53852 KB Output is correct
10 Correct 8 ms 49500 KB Output is correct
11 Correct 8 ms 49500 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 8 ms 53592 KB Output is correct
14 Correct 8 ms 49500 KB Output is correct
15 Correct 9 ms 49364 KB Output is correct
16 Correct 8 ms 49496 KB Output is correct
17 Correct 8 ms 49496 KB Output is correct
18 Correct 7 ms 49500 KB Output is correct
19 Correct 8 ms 49500 KB Output is correct
20 Correct 511 ms 145384 KB Output is correct
21 Correct 343 ms 161872 KB Output is correct
22 Correct 209 ms 146868 KB Output is correct
23 Correct 179 ms 136436 KB Output is correct
24 Correct 204 ms 147024 KB Output is correct
25 Correct 676 ms 176048 KB Output is correct
26 Correct 265 ms 145492 KB Output is correct
27 Correct 586 ms 202064 KB Output is correct
28 Correct 211 ms 108392 KB Output is correct
29 Correct 109 ms 85588 KB Output is correct
30 Correct 196 ms 101156 KB Output is correct
31 Correct 92 ms 90964 KB Output is correct
32 Correct 94 ms 92096 KB Output is correct
33 Correct 116 ms 93264 KB Output is correct
34 Correct 89 ms 91216 KB Output is correct
35 Correct 322 ms 84992 KB Output is correct
36 Correct 12 ms 53520 KB Output is correct
37 Correct 52 ms 68436 KB Output is correct
38 Execution timed out 4033 ms 74832 KB Time limit exceeded
39 Halted 0 ms 0 KB -