oj.uz

Submission #283323

# Submission time Handle Problem Language Result Execution time Memory
283323 2020-08-25T14:25:37 Z Kastanda Sky Walking (IOI19_walk) C++14
100 / 100
 1382 ms 157096 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41088 KB Output is correct
2 Correct 31 ms 41088 KB Output is correct
3 Correct 32 ms 41080 KB Output is correct
4 Correct 24 ms 41016 KB Output is correct
5 Correct 24 ms 41088 KB Output is correct
6 Correct 30 ms 41120 KB Output is correct
7 Correct 25 ms 41088 KB Output is correct
8 Correct 24 ms 41088 KB Output is correct
9 Correct 23 ms 41088 KB Output is correct
10 Correct 24 ms 41088 KB Output is correct
11 Correct 24 ms 41088 KB Output is correct
12 Correct 27 ms 41088 KB Output is correct
13 Correct 26 ms 41088 KB Output is correct
14 Correct 26 ms 41088 KB Output is correct
15 Correct 27 ms 41080 KB Output is correct
16 Correct 26 ms 41088 KB Output is correct
17 Correct 26 ms 41088 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 41088 KB Output is correct
2 Correct 25 ms 41088 KB Output is correct
3 Correct 435 ms 106168 KB Output is correct
4 Correct 507 ms 103648 KB Output is correct
5 Correct 337 ms 92280 KB Output is correct
6 Correct 350 ms 86284 KB Output is correct
7 Correct 343 ms 92280 KB Output is correct
8 Correct 472 ms 109356 KB Output is correct
9 Correct 492 ms 103904 KB Output is correct
10 Correct 561 ms 108148 KB Output is correct
11 Correct 431 ms 97924 KB Output is correct
12 Correct 290 ms 74104 KB Output is correct
13 Correct 532 ms 109692 KB Output is correct
14 Correct 323 ms 70904 KB Output is correct
15 Correct 339 ms 72496 KB Output is correct
16 Correct 305 ms 73464 KB Output is correct
17 Correct 317 ms 72080 KB Output is correct
18 Correct 349 ms 72256 KB Output is correct
19 Correct 34 ms 42488 KB Output is correct
20 Correct 127 ms 55288 KB Output is correct
21 Correct 272 ms 71372 KB Output is correct
22 Correct 267 ms 73084 KB Output is correct
23 Correct 399 ms 80628 KB Output is correct
24 Correct 298 ms 72912 KB Output is correct
25 Correct 297 ms 72320 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 53368 KB Output is correct
2 Correct 609 ms 109084 KB Output is correct
3 Correct 758 ms 108792 KB Output is correct
4 Correct 883 ms 110328 KB Output is correct
5 Correct 1111 ms 110764 KB Output is correct
6 Correct 931 ms 106024 KB Output is correct
7 Correct 362 ms 79736 KB Output is correct
8 Correct 299 ms 69980 KB Output is correct
9 Correct 880 ms 105200 KB Output is correct
10 Correct 407 ms 93392 KB Output is correct
11 Correct 48 ms 42616 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 53368 KB Output is correct
2 Correct 609 ms 109084 KB Output is correct
3 Correct 758 ms 108792 KB Output is correct
4 Correct 883 ms 110328 KB Output is correct
5 Correct 1111 ms 110764 KB Output is correct
6 Correct 931 ms 106024 KB Output is correct
7 Correct 362 ms 79736 KB Output is correct
8 Correct 299 ms 69980 KB Output is correct
9 Correct 880 ms 105200 KB Output is correct
10 Correct 407 ms 93392 KB Output is correct
11 Correct 48 ms 42616 KB Output is correct
12 Correct 729 ms 108920 KB Output is correct
13 Correct 647 ms 109688 KB Output is correct
14 Correct 1040 ms 110836 KB Output is correct
15 Correct 701 ms 99784 KB Output is correct
16 Correct 687 ms 108148 KB Output is correct
17 Correct 721 ms 108148 KB Output is correct
18 Correct 657 ms 99804 KB Output is correct
19 Correct 703 ms 108276 KB Output is correct
20 Correct 371 ms 78968 KB Output is correct
21 Correct 68 ms 44664 KB Output is correct
22 Correct 388 ms 95120 KB Output is correct
23 Correct 426 ms 93816 KB Output is correct
24 Correct 342 ms 77560 KB Output is correct
25 Correct 408 ms 90232 KB Output is correct
26 Correct 299 ms 67064 KB Output is correct
27 Correct 1045 ms 112236 KB Output is correct
28 Correct 518 ms 109816 KB Output is correct
29 Correct 966 ms 106080 KB Output is correct
30 Correct 359 ms 79556 KB Output is correct
31 Correct 878 ms 105200 KB Output is correct
32 Correct 344 ms 77684 KB Output is correct
33 Correct 344 ms 79028 KB Output is correct
34 Correct 404 ms 84204 KB Output is correct
35 Correct 415 ms 80760 KB Output is correct
36 Correct 326 ms 75900 KB Output is correct
37 Correct 265 ms 68600 KB Output is correct
38 Correct 260 ms 70008 KB Output is correct
39 Correct 396 ms 77688 KB Output is correct
40 Correct 315 ms 69952 KB Output is correct
41 Correct 298 ms 69624 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41088 KB Output is correct
2 Correct 31 ms 41088 KB Output is correct
3 Correct 32 ms 41080 KB Output is correct
4 Correct 24 ms 41016 KB Output is correct
5 Correct 24 ms 41088 KB Output is correct
6 Correct 30 ms 41120 KB Output is correct
7 Correct 25 ms 41088 KB Output is correct
8 Correct 24 ms 41088 KB Output is correct
9 Correct 23 ms 41088 KB Output is correct
10 Correct 24 ms 41088 KB Output is correct
11 Correct 24 ms 41088 KB Output is correct
12 Correct 27 ms 41088 KB Output is correct
13 Correct 26 ms 41088 KB Output is correct
14 Correct 26 ms 41088 KB Output is correct
15 Correct 27 ms 41080 KB Output is correct
16 Correct 26 ms 41088 KB Output is correct
17 Correct 26 ms 41088 KB Output is correct
18 Correct 25 ms 41088 KB Output is correct
19 Correct 25 ms 41088 KB Output is correct
20 Correct 435 ms 106168 KB Output is correct
21 Correct 507 ms 103648 KB Output is correct
22 Correct 337 ms 92280 KB Output is correct
23 Correct 350 ms 86284 KB Output is correct
24 Correct 343 ms 92280 KB Output is correct
25 Correct 472 ms 109356 KB Output is correct
26 Correct 492 ms 103904 KB Output is correct
27 Correct 561 ms 108148 KB Output is correct
28 Correct 431 ms 97924 KB Output is correct
29 Correct 290 ms 74104 KB Output is correct
30 Correct 532 ms 109692 KB Output is correct
31 Correct 323 ms 70904 KB Output is correct
32 Correct 339 ms 72496 KB Output is correct
33 Correct 305 ms 73464 KB Output is correct
34 Correct 317 ms 72080 KB Output is correct
35 Correct 349 ms 72256 KB Output is correct
36 Correct 34 ms 42488 KB Output is correct
37 Correct 127 ms 55288 KB Output is correct
38 Correct 272 ms 71372 KB Output is correct
39 Correct 267 ms 73084 KB Output is correct
40 Correct 399 ms 80628 KB Output is correct
41 Correct 298 ms 72912 KB Output is correct
42 Correct 297 ms 72320 KB Output is correct
43 Correct 114 ms 53368 KB Output is correct
44 Correct 609 ms 109084 KB Output is correct
45 Correct 758 ms 108792 KB Output is correct
46 Correct 883 ms 110328 KB Output is correct
47 Correct 1111 ms 110764 KB Output is correct
48 Correct 931 ms 106024 KB Output is correct
49 Correct 362 ms 79736 KB Output is correct
50 Correct 299 ms 69980 KB Output is correct
51 Correct 880 ms 105200 KB Output is correct
52 Correct 407 ms 93392 KB Output is correct
53 Correct 48 ms 42616 KB Output is correct
54 Correct 729 ms 108920 KB Output is correct
55 Correct 647 ms 109688 KB Output is correct
56 Correct 1040 ms 110836 KB Output is correct
57 Correct 701 ms 99784 KB Output is correct
58 Correct 687 ms 108148 KB Output is correct
59 Correct 721 ms 108148 KB Output is correct
60 Correct 657 ms 99804 KB Output is correct
61 Correct 703 ms 108276 KB Output is correct
62 Correct 371 ms 78968 KB Output is correct
63 Correct 68 ms 44664 KB Output is correct
64 Correct 388 ms 95120 KB Output is correct
65 Correct 426 ms 93816 KB Output is correct
66 Correct 342 ms 77560 KB Output is correct
67 Correct 408 ms 90232 KB Output is correct
68 Correct 299 ms 67064 KB Output is correct
69 Correct 1045 ms 112236 KB Output is correct
70 Correct 518 ms 109816 KB Output is correct
71 Correct 966 ms 106080 KB Output is correct
72 Correct 359 ms 79556 KB Output is correct
73 Correct 878 ms 105200 KB Output is correct
74 Correct 344 ms 77684 KB Output is correct
75 Correct 344 ms 79028 KB Output is correct
76 Correct 404 ms 84204 KB Output is correct
77 Correct 415 ms 80760 KB Output is correct
78 Correct 326 ms 75900 KB Output is correct
79 Correct 265 ms 68600 KB Output is correct
80 Correct 260 ms 70008 KB Output is correct
81 Correct 396 ms 77688 KB Output is correct
82 Correct 315 ms 69952 KB Output is correct
83 Correct 298 ms 69624 KB Output is correct
84 Correct 101 ms 52016 KB Output is correct
85 Correct 734 ms 113688 KB Output is correct
86 Correct 1193 ms 129072 KB Output is correct
87 Correct 87 ms 51684 KB Output is correct
88 Correct 91 ms 52344 KB Output is correct
89 Correct 88 ms 51472 KB Output is correct
90 Correct 46 ms 45436 KB Output is correct
91 Correct 26 ms 41216 KB Output is correct
92 Correct 53 ms 44152 KB Output is correct
93 Correct 246 ms 71124 KB Output is correct
94 Correct 70 ms 46844 KB Output is correct
95 Correct 419 ms 101684 KB Output is correct
96 Correct 383 ms 98040 KB Output is correct
97 Correct 343 ms 81144 KB Output is correct
98 Correct 369 ms 93948 KB Output is correct
99 Correct 1382 ms 157096 KB Output is correct
100 Correct 698 ms 114784 KB Output is correct
101 Correct 932 ms 121060 KB Output is correct
102 Correct 293 ms 82684 KB Output is correct
103 Correct 346 ms 80748 KB Output is correct
104 Correct 334 ms 82216 KB Output is correct
105 Correct 404 ms 86396 KB Output is correct
106 Correct 391 ms 81264 KB Output is correct
107 Correct 358 ms 75384 KB Output is correct
108 Correct 66 ms 46584 KB Output is correct
109 Correct 724 ms 97904 KB Output is correct
110 Correct 567 ms 112736 KB Output is correct
111 Correct 533 ms 113120 KB Output is correct
112 Correct 416 ms 85240 KB Output is correct
113 Correct 360 ms 81272 KB Output is correct