#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
int n = x.size();
int m = l.size();
ll ans = LLONG_MAX;
bool st3 = (s == 0) && (g == n - 1);
for(int i = 0; i < n; i++)
st3 &= h[i] == h[0];
if(st3){
set<pair<ll, ll>> act;
vector<set<pair<ll, ll>>> skywalks(n);
for(int i = 0; i < m; i++){
skywalks[l[i]].insert(make_pair(0, y[i]));
}
for(int i = 0; i < m; i++){
auto it = skywalks[r[i]].lower_bound(make_pair(0, y[i]));
if(it != skywalks[r[i]].end() && it->second == y[i] && it->first == 0){
skywalks[r[i]].erase(it);
}
else{
skywalks[r[i]].insert(make_pair(1, y[i]));
}
}
for(auto [a, b] : skywalks[0]){
act.insert({a, a});
}
for(int i = 0; i < n; i++){
// cout << "BUILDING: " << i << endl;
// for(auto [a, b] : act){
// cout << "HEIGHT: " << a << " COST: " << b << endl;
// }
for(auto [b, a] : skywalks[i]){
if(b == 0){
ll minh = 1e16;
auto it = act.lower_bound(make_pair(a, -1));
if(it != act.end()){
minh = min(minh, it->second + abs(a - it->first));
}
if(it != act.begin()){
it = prev(it);
minh = min(minh, it->second + abs(a - it->first));
}
act.insert(make_pair(a, minh));
}
else{
auto it = act.lower_bound(make_pair(a, -1));
ll cur = it->second;
if(i == n - 1){
ans = min(ans, cur + a);
}
assert(it->first == a);
act.erase(it);
it = act.lower_bound(make_pair(a, -1));
if(it != act.end()){
ll curheight = it->first;
ll minh = min(it->second, cur + abs(it->first - a));
act.erase(it);
act.insert(make_pair(curheight, minh));
}
it = act.lower_bound(make_pair(a, -1));
if(it != act.begin()){
it = prev(it);
ll curheight = it->first;
ll minh = min(it->second, cur + abs(curheight - a));
act.erase(it);
act.insert(make_pair(curheight, minh));
}
}
}
}
return ans + x[g] - x[s];
}
return 0;
}
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:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for(auto [a, b] : skywalks[0]){
| ^
walk.cpp:41:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for(auto [b, a] : skywalks[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
5208 KB |
Output is correct |
| 2 |
Incorrect |
130 ms |
15708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
5208 KB |
Output is correct |
| 2 |
Incorrect |
130 ms |
15708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
