You need to find the shortest distance from 1 to each node. The statement has been updated. Sorry for the mistake.
New Vegas is a city made up of $n$ districtes, each districte has a value $a_i$ attached to it, $\textbf{the array $a$ is sorted and unique}$.
Due to nuclear fallout, all the edges were destroyed, in an attempt to fix the edges the government decided to do $q$ reconstruction plans. Each plan is of the form $(a,b,c)$ where a directed edge is added from $a$ to all cities in the range $(b,c)$.
The weight on an edges going from $i$ to $j$ is $|a_i - a_j|$.
Find the shortest distance between $1$ and the other nodes, if a node is unreachable print $-1$.
The first line of input contains two integers $n, q$ $(1 \leq n,q \leq 10^5)$, the number of nodes, and the number of reconstruction plans.
The second line contains $n$ $\textbf{unique}$ $\textbf{sorted}$ array $a$ $(1 \leq a_i \leq 10^9)$
The last $q$ lines contain three integers each $a, b, c$ $(1 \leq a \leq n, 1 \leq b \leq c \leq n)$
Print $n$ integers, where the $i^{th} $ integer is the distance from $1$ to $i$.
| Input | Output |
|---|---|
6 3 1 2 3 4 5 6 1 3 3 2 1 4 3 2 2 Copy
|
0 3 2 5 -1 -1 Copy
|
Let's consider the distance to be $1$ between all nodes then to solve this problem we can simply create a segment tree and connect $a$ to the nodes in the segment tree covering the range $(b,c)$, with weight $1$ and set the weights on the edges in the segment tree to $0$.
To deal with the distance portion of the problem, when adding an edge from $x$ to a node $c$ in the segment tree covering the range $(l,r)$, give that edge weight of $|a_x - a_l|$.
Also, when building the tree when adding an edges from the node covering $(l,r)$ to the node covering $(l, \frac{l + r}{2})$ give that edge a weight of $0$, but when adding an edge to $(\frac{l + r}{2} + 1,r)$ give that edge a weight of $|a_l - a_{\frac{l + r}{2} + 1}|$.
You need to use two segment trees one for moving from left to right and the other to move from right to left, they both use the same logic mentioned above but with slightly different variables in each equation.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const long long oo = 1e18;
int n,q,a[N];
long long dis[10*N];
vector<pair<int,int>>v[10*N];
void build(int c,int l,int r){
if(l == r){
v[c + n].push_back({l,0});
return;
}
int mid = (l + r)/2 + 1;
v[c + n].push_back({2*c + 1 + n,0});
v[c + n].push_back({2*c + 2 + n,a[mid] - a[l]});
build(2*c + 1,l,(l + r)/2);
build(2*c + 2,(l + r)/2 + 1,r);
}
void build1(int c,int l,int r){
if(l == r){
v[c + 5*n].push_back({l,0});
return;
}
int mid = (l + r)/2;
v[c + 5*n].push_back({2*c + 1 + 5*n,a[r] - a[mid]});
v[c + 5*n].push_back({2*c + 2 + 5*n,0});
build1(2*c + 1,l,(l + r)/2);
build1(2*c + 2,(l + r)/2 + 1,r);
}
void add(int c,int l,int r,int s,int e,int from){
if(r < s || e < l)return;
if(s <= l && r <= e && (from <= l || r <= from)){
if(from <= l)v[from].push_back({c + n,a[l] - a[from]});
else v[from].push_back({c + 5*n,a[from] - a[r]});
return;
}
add(2*c + 1,l,(l + r)/2,s,e,from);
add(2*c + 2,(l + r)/2 + 1,r,s,e,from);
}
void dijk(){
priority_queue<pair<long long,int>>q;
q.push({0,0});
dis[0] = 0;
while(!q.empty()){
int x = q.top().second;
long long y = -q.top().first;
q.pop();
if(y > dis[x])continue;
for(auto i : v[x])
if(dis[i.first] > y + i.second){
dis[i.first] = y + i.second;
q.push({-dis[i.first],i.first});
}
}
}
int main(){
for(int i = 0;i < 10*N;i++)dis[i] = 1e18;
scanf("%d%d",&n,&q);
for(int i = 0;i < n;i++)scanf("%d",a + i);
build(0,0,n - 1);
build1(0,0,n - 1);
for(int i = 0,a,b,c;i < q;i++){
scanf("%d%d%d",&a,&;b,&;c);
a--;b--;c--;
add(0,0,n - 1,b,c,a);
}
dijk();
for(int i = 0;i < n;i++){
if(dis[i] == oo)dis[i] = -1;
printf("%lld ",dis[i]);
}
}