#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct skywalk
{
int left, right;
ll height;
skywalk(int _left = 0, int _right = 0, ll _height = 0)
{
left = _left;
right = _right;
height = _height;
}
}sky[maxn];
bool cmp(const skywalk &sk1, const skywalk &sk2)
{
return sk1.height < sk2.height;
}
const ll inf = 1e18;
struct node
{
ll down_sum, up_sum;
node(ll _down_sum = inf, ll _up_sum = inf)
{
down_sum = _down_sum;
up_sum = _up_sum;
}
};
node merge_nodes(node lf, node rf)
{
node nd;
nd.down_sum = min(lf.down_sum, rf.down_sum);
nd.up_sum = min(lf.up_sum, rf.up_sum);
return nd;
}
node tree[4 * maxn];
int is_active[maxn];
ll dp[maxn];
void toggle(int root, int left, int right, int pos)
{
if (left == right)
{
is_active[left] ^= 1;
///cout << root << " : " << left << " : " << right << " : " << pos << " " << is_active[left] << endl;
if (is_active[left])
{
tree[root].down_sum = - sky[left].height + dp[left];
tree[root].up_sum = sky[left].height + dp[left];
///cout << "activate " << left << " " << sky[left].height << endl;
}
else
{
tree[root] = node();
}
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
toggle(root * 2, left, mid, pos);
else
toggle(root * 2 + 1, mid + 1, right, pos);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
///cout << "here " << left << " " << right << " " << tree[root].up_sum << endl;
}
node query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_nodes(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
int n, m;
ll x[maxn], h[maxn];
vector < pair < int, int > > upd[maxn];
ll state[100][100];
bool intersects(int idx, int pos)
{
if (sky[idx].left <= pos && sky[idx].right >= pos && sky[idx].height <= h[pos])
return true;
return false;
}
void relax_state(int i)
{
for (int p1 = 0; p1 < m; p1 ++)
{
if (!intersects(p1, i))
continue;
for (int p2 = 0; p2 < m; p2 ++)
{
if (!intersects(p2, i))
continue;
state[i][p2] = min(state[i][p2], state[i][p1] + abs(sky[p1].height - sky[p2].height));
}
}
}
long long min_distance(vector<int> X, vector<int> H, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
n = X.size();
m = l.size();
for (int i = 0; i < n; i ++)
x[i] = X[i], h[i] = H[i];
for (int i = 0; i < m; i ++)
{
sky[i] = skywalk(l[i], r[i], y[i]);
}
sort(sky, sky + m, cmp);
if (n <= 50 && m <= 50)
{
if (s > g)
swap(s, g);
/**cout << "skywalk" << endl;
for (int j = 0; j < m; j ++)
{
cout << j << " : " << sky[j].left << " " << sky[j].right << " " << sky[j].height << endl;
}
cout << "------------" << endl;*/
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
state[i][j] = inf;
for (int j = 0; j < m; j ++)
{
if (intersects(j, s))
state[s][j] = sky[j].height;
}
/**for (int i = s - 1; i >= 0; i --)
{
for (int j = i + 1; j <= s; j ++)
{
for (int p = 0; p < m; p ++)
{
if (intersects(p, i) && intersects(p, j))
{
state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
}
}
}
relax_state(i);
}*/
/**for (int j = 0; j < m; j ++)
cout << state[s][j] << " ";
cout << endl;*/
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < i; j ++)
{
for (int p = 0; p < m; p ++)
{
if (intersects(p, i) && intersects(p, j))
{
state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
}
}
}
relax_state(i);
}
for (int i = n - 1; i >= g; i --)
{
for (int j = n - 1; j > i; j --)
{
for (int p = 0; p < m; p ++)
{
if (intersects(p, i) && intersects(p, j))
{
state[i][p] = min(state[i][p], state[j][p] + abs(x[j] - x[i]));
}
}
}
relax_state(i);
}
ll ans = inf;
for (int j = 0; j < m; j ++)
{
if (state[g][j] != inf)
ans = min(ans, state[g][j] + sky[j].height);
}
if (ans == inf)
return -1;
return ans;
}
if (s != 0 || g != n - 1)
return 0;
for (int i = 0; i < m; i ++)
{
upd[sky[i].left].push_back({i, 1});
}
for (int i = 0; i < m; i ++)
{
upd[sky[i].right].push_back({i, -1});
}
for (pair < int, int > cur : upd[s])
{
dp[cur.first] = sky[cur.first].height;
toggle(1, 0, m - 1, cur.first);
///cout << "here" << endl;
}
///cout << tree[1].up_sum << endl;
for (int i = 1; i < g; i ++)
{
for (pair < int, int > cur : upd[i])
{
if (cur.second == 1)
{
node under = node(), above = node();
if (cur.first != 0)
under = query(1, 0, m - 1, 0, cur.first - 1);
if (cur.first != m - 1)
above = query(1, 0, m - 1, cur.first + 1, m - 1);
//cout << under.down_sum << " " << above.up_sum << endl;
if (under.down_sum == inf && above.up_sum == inf)
dp[cur.first] = inf;
else
dp[cur.first] = min(sky[cur.first].height + under.down_sum, above.up_sum - sky[cur.first].height);
///cout << cur.first << " :: " << dp[cur.first] << endl;
}
toggle(1, 0, m - 1, cur.first);
}
}
node ans = tree[1];
if (ans.up_sum == inf)
return -1;
return ans.up_sum + x[g] - x[s];
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:134:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
134 | if (s > g)
| ^~
walk.cpp:143:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
143 | for (int i = 0; i < n; i ++)
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10404 KB |
Output is correct |
2 |
Correct |
6 ms |
10452 KB |
Output is correct |
3 |
Correct |
5 ms |
10452 KB |
Output is correct |
4 |
Correct |
7 ms |
10452 KB |
Output is correct |
5 |
Correct |
5 ms |
10452 KB |
Output is correct |
6 |
Correct |
6 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
5 ms |
10452 KB |
Output is correct |
9 |
Correct |
5 ms |
10452 KB |
Output is correct |
10 |
Correct |
5 ms |
10452 KB |
Output is correct |
11 |
Correct |
6 ms |
10452 KB |
Output is correct |
12 |
Correct |
5 ms |
10452 KB |
Output is correct |
13 |
Correct |
5 ms |
10452 KB |
Output is correct |
14 |
Correct |
5 ms |
10452 KB |
Output is correct |
15 |
Correct |
5 ms |
10452 KB |
Output is correct |
16 |
Correct |
5 ms |
10452 KB |
Output is correct |
17 |
Correct |
6 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
10452 KB |
Output is correct |
2 |
Correct |
5 ms |
10480 KB |
Output is correct |
3 |
Incorrect |
48 ms |
13160 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
13908 KB |
Output is correct |
2 |
Correct |
140 ms |
16332 KB |
Output is correct |
3 |
Correct |
131 ms |
16972 KB |
Output is correct |
4 |
Correct |
182 ms |
20720 KB |
Output is correct |
5 |
Correct |
183 ms |
20368 KB |
Output is correct |
6 |
Correct |
174 ms |
20680 KB |
Output is correct |
7 |
Correct |
94 ms |
17632 KB |
Output is correct |
8 |
Correct |
216 ms |
20384 KB |
Output is correct |
9 |
Correct |
186 ms |
20684 KB |
Output is correct |
10 |
Correct |
134 ms |
19660 KB |
Output is correct |
11 |
Correct |
15 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
13908 KB |
Output is correct |
2 |
Correct |
140 ms |
16332 KB |
Output is correct |
3 |
Correct |
131 ms |
16972 KB |
Output is correct |
4 |
Correct |
182 ms |
20720 KB |
Output is correct |
5 |
Correct |
183 ms |
20368 KB |
Output is correct |
6 |
Correct |
174 ms |
20680 KB |
Output is correct |
7 |
Correct |
94 ms |
17632 KB |
Output is correct |
8 |
Correct |
216 ms |
20384 KB |
Output is correct |
9 |
Correct |
186 ms |
20684 KB |
Output is correct |
10 |
Correct |
134 ms |
19660 KB |
Output is correct |
11 |
Correct |
15 ms |
11988 KB |
Output is correct |
12 |
Correct |
158 ms |
17108 KB |
Output is correct |
13 |
Correct |
218 ms |
20632 KB |
Output is correct |
14 |
Correct |
183 ms |
20252 KB |
Output is correct |
15 |
Correct |
207 ms |
20684 KB |
Output is correct |
16 |
Correct |
177 ms |
20628 KB |
Output is correct |
17 |
Correct |
177 ms |
20624 KB |
Output is correct |
18 |
Correct |
163 ms |
20568 KB |
Output is correct |
19 |
Correct |
176 ms |
20512 KB |
Output is correct |
20 |
Correct |
128 ms |
17632 KB |
Output is correct |
21 |
Correct |
29 ms |
13652 KB |
Output is correct |
22 |
Correct |
151 ms |
19448 KB |
Output is correct |
23 |
Correct |
150 ms |
19744 KB |
Output is correct |
24 |
Correct |
175 ms |
19864 KB |
Output is correct |
25 |
Correct |
146 ms |
19476 KB |
Output is correct |
26 |
Correct |
144 ms |
19984 KB |
Output is correct |
27 |
Correct |
185 ms |
20520 KB |
Output is correct |
28 |
Correct |
203 ms |
20624 KB |
Output is correct |
29 |
Correct |
183 ms |
20632 KB |
Output is correct |
30 |
Correct |
99 ms |
17648 KB |
Output is correct |
31 |
Correct |
166 ms |
20796 KB |
Output is correct |
32 |
Correct |
139 ms |
20044 KB |
Output is correct |
33 |
Correct |
155 ms |
20004 KB |
Output is correct |
34 |
Correct |
120 ms |
20176 KB |
Output is correct |
35 |
Correct |
142 ms |
20172 KB |
Output is correct |
36 |
Correct |
192 ms |
20568 KB |
Output is correct |
37 |
Correct |
162 ms |
19960 KB |
Output is correct |
38 |
Correct |
145 ms |
20268 KB |
Output is correct |
39 |
Correct |
101 ms |
20748 KB |
Output is correct |
40 |
Correct |
164 ms |
20300 KB |
Output is correct |
41 |
Correct |
153 ms |
20312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10404 KB |
Output is correct |
2 |
Correct |
6 ms |
10452 KB |
Output is correct |
3 |
Correct |
5 ms |
10452 KB |
Output is correct |
4 |
Correct |
7 ms |
10452 KB |
Output is correct |
5 |
Correct |
5 ms |
10452 KB |
Output is correct |
6 |
Correct |
6 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
5 ms |
10452 KB |
Output is correct |
9 |
Correct |
5 ms |
10452 KB |
Output is correct |
10 |
Correct |
5 ms |
10452 KB |
Output is correct |
11 |
Correct |
6 ms |
10452 KB |
Output is correct |
12 |
Correct |
5 ms |
10452 KB |
Output is correct |
13 |
Correct |
5 ms |
10452 KB |
Output is correct |
14 |
Correct |
5 ms |
10452 KB |
Output is correct |
15 |
Correct |
5 ms |
10452 KB |
Output is correct |
16 |
Correct |
5 ms |
10452 KB |
Output is correct |
17 |
Correct |
6 ms |
10452 KB |
Output is correct |
18 |
Correct |
5 ms |
10452 KB |
Output is correct |
19 |
Correct |
5 ms |
10480 KB |
Output is correct |
20 |
Incorrect |
48 ms |
13160 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |