#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 = 1e5+100, K = 20;
int n, m;
map<pair<int, int>, int> node;
vector<pair<int,int>> G[N];
vector<int> F[N];
vector<pair<int, ll>> g[N];
int rmq[N][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);
G[u].pb({v, L});
G[v].pb({u, L});
}
for(int i = 1; i <= n; ++i) rmq[i][0] = x[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){
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(p == u) break;
if(h[p] >= w){
node[{p, w}] = co++;
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());
for(int p: F[i]){
// cout << i << ' ' <<p << '\n';
node[{i, p}] = co++;
}
for(int j = 0; j + 1 < F[i].size(); ++j){
// cout << F[i][j] << ' ';
g[node[{i, F[i][j]}]].pb({node[{i, F[i][j + 1]}], F[i][j + 1] - F[i][j]});
g[node[{i, F[i][j + 1]}]].pb({node[{i, F[i][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;
for(int j = i; j <= u; ++j){
if(h[j] >= w){
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:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = l+r>>1;
| ~^~
walk.cpp:78:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j = 0; j + 1 < F[i].size(); ++j){
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
27988 KB |
Output is correct |
| 2 |
Runtime error |
922 ms |
401748 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
27988 KB |
Output is correct |
| 2 |
Runtime error |
922 ms |
401748 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
