#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 2e6+100, K = 20, M=2E5;
int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<pair<int,int>> T[N];
vector<int> F[N];
vector<pair<int, ll>> g[N];
int rmq[M][K];
int get(int l, int r){
int k = log2(r-l+1);
return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
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 gg) {
n = x.size();
m = l.size();
for(int i = 0; i < m; ++i){
int u = l[i], v = r[i], L = y[i];
// F[u].pb(L);
// F[v].pb(L);
if(u>v) swap(u,v);
G[u].pb({v, L});
T[v].pb({u, L});
}
if(s == 0 && gg == n-1){
set<pair<ll, ll>> S;
S.insert({0, 0});
for(auto u: G[0]){
S.insert({u.ss, u.ss});
}
for(int i = 1; i < n; ++i){
vector<pair<ll, ll>> ins;
for(auto U: G[i]){
ll u = U.ff;
auto it = S.lower_bound(pair<ll,ll>{u, 0ll});
ll val = 1e15;
if(it != S.end()){
val = min(val, abs((*it).first - u) + (*it).second);
}
if(it != S.begin()){ it = prev(it);
val = min(val, abs((*it).first - u) + (*it).second);
}
ins.pb({u, val});
}
for(auto U : T[i]){
int u = U.first;
auto it = S.lower_bound(pair<ll,ll>{u, 0ll});
if(it != S.end() && (*it).first == u){
S.erase(it);
}
}
for(auto p: ins) S.insert(p);
}
ll uwu = 1e15;
for(auto x: S){
uwu=min(uwu, x.ss + x.ff);
}
return x[n-1]-x[0] + uwu;
}
for(int i = 1; i <= n; ++i) rmq[i][0] = h[i - 1];
for(int j = 1; j < K ;++j){
for(int i = 1; i + (1<<j) <= n+1; ++i){
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<(j-1))][j-1]);
}
}
int co = 0;
for(int i = 0; i < n; ++i){
for(auto U: G[i]){
int u = U.ff; ll w = U.ss;
if(u > i){
if(node[{i,w}] == 0)
node[{i, w}] = co++;
int last = i;
while(last < u){
int l = last + 2, r = n, p = n + 1;
while(l <= r){
int mid = l+r>>1;
if(get(last + 2, mid) >= w){
p = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
--p;
if(h[p] >= w){
if(node[{p,w}]==0)
node[{p, w}] = co++;
// cout << x[p] << ' ' << x[last] << '\n';
g[node[{last, w}]].pb({node[{p,w}], abs(x[p] - x[last])});
g[node[{p,w}]].pb({node[{last, w}], abs(x[p] - x[last])});
F[p].pb(w);
}
last = p;
}
}
}
}
for(int i = 0; i < n; ++i){
F[i].pb(0);
// F[i].pb(h[i]);
sort(all(F[i]));
F[i].erase(unique(all(F[i])), F[i].end());
vector<int> X;
if(node[{i,0}]==0) node[{i, 0}] = co++;
// if(node[{i,h[i]}]==0) node[{i, 0}] = co++;
for(int p: F[i]){
// cout << i << ' ' <<p << '\n';
// node[{i, p}] = co++;
X.pb(node[{i, p}]);
}
for(int j = 0; j + 1 < F[i].size(); ++j){
// cout << F[i][j] << ' ';
g[X[j]].pb({X[j+1], F[i][j + 1] - F[i][j]});
g[X[j + 1]].pb({X[j], F[i][j + 1] - F[i][j]});
}
// cout << '\n';
}
// cout << "\n";
// for(int i = 0; i < n; ++i){
// for(auto U: G[i]){
// int u = U.ff; ll w = U.ss;
// if(u > i){
// int last = i;
// int j = u;
// g[node[{last, w}]].pb({node[{j, w}], abs(x[j]-x[last])});
// g[node[{j, w}]].pb({node[{last, w}], abs(x[j]-x[last])});
// last = j;
// }
// }
// }
vector<ll> dist(co, 1e15*1ll);
vector<bool> vis(co);
priority_queue<pair<ll, int>> Q;
Q.push({0, node[{s, 0}]});
dist[node[{s, 0}]] = 0;
while(!Q.empty()){
int v = Q.top().ss; Q.pop();
if(vis[v]) continue;
// cout << v << ' ' << dist[v] << '\n';
vis[v] = 1;
for(auto U: g[v]){
int u = U.ff;
ll w= U.ss;
if(dist[u] > dist[v] + w){
dist[u] = dist[v] + w;;
Q.push({-dist[u], u});
}
}
}
ll D = dist[node[{gg, 0}]];
if(D == 1e15*1ll) return -1;
// cout << node[{gg,0}] << ' ';
return D;
}
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:94:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = l+r>>1;
| ~^~
walk.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int j = 0; j + 1 < F[i].size(); ++j){
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
188316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
188252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
190996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
190996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
188316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
