All Tracks>Data Structures> Advanced Data Structures> Segment Trees> Problem
Optimal Moves
★★★★★

4.6

5 votes
Dynamic Programming, Segment Trees, Advanced Data Structures, Segment tree, Data Structures
Problem

There are N points placed on a number line at position 1,2,...,N.

Initially, you are at point 1 and want to find the minimum cost to reach each of the N points. You are allowed to move only towards +ve x-axis.

Let's say, after certain moves, you are at point i(<N) and want to make the next move. You are allowed to make a move only of the following two types: 

  • type 1: by moving to the next point i.e point i+1 which cost Ai.
  • type 2: by moving to point j if and only if i∈[Lj,Rj] which cost Bi. 

Find the minimum cost to reach each of the N points.

Input Format

  • The first line contains T denoting the number of test cases. The description of T test cases is as follows:
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains one integer N — the number of points.
    • The second line consists of N−1 space-separated integers denoting the elements of array A.
    • The Third line consists of N space-separated integers denoting the elements of array B.
    • The Fourth line consists of N space-separated integers denoting the elements of array L.
    • The Fifth line consists of N space-separated integers denoting the elements of array R.

Output Format

  • For each test case, output on a new line, the minimum cost to reach each of the N points.

Constraints

  • 1≤T≤105
  • 2≤N≤2⋅105
  • 1≤Ai,Bi≤109
  • 1≤Li≤Ri≤i
  •  It is guaranteed that sum of N over all test cases doesn't exceed  2⋅105
Sample Input
2
5
5 3 1 1
4 2 4 1 1
1 1 2 1 3
1 2 2 4 5
6
6 8 5 10 5
7 4 5 3 8 1
1 1 2 2 1 4
1 2 3 4 3 5
Sample Output
0 4 6 4 5
0 6 10 10 7 12
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Test case 1: 

  • You are initially at point 1 ( cost=0 ).

  • The only way to reach point 2 is by using move 1→2.

    • Since, point 2 is next to point 1 so we can perform the move 1→2 using move of type 1 with the cost of A1=5.

    • Also, 1∈[L2=1,R2=2] so we can perform the move 1→2 using move of type 2 with the cost of B1=4.

    • Hence, the minimum cost is min(5,4)=4.

  • The only way to reach point 3 is by using moves 1→2→3 because we can't move directly 1→3 since, 1∉[L3=2,R3=2].

    • We have already found the optimal way to reach point 2 with the minimum cost of 4 above.

    • Now, to reach from 2→3, we again have both types of move possible because point 3 is next to point 2 and also 2∈[L3=2,R3=2].

    • For move 2→3, move of type 1 costs A2=3 and move of type 2 costs B2=2. 

    • Hence, the minimum cost is 4+min(3,2)=4+2=6. 

Contributers:
Editor Image

?