409971: GYM103870 P Waku-Waku Abyss

1900 years ago, a colossal pit was discovered on an island. The abyss is 1000 meters in diameter and at least 20,000 meters deep — at least because none have reached the bottom. The allure of the Abyss is inescapable, so Riko has decided to embark on the adventure of a lifetime.

Riko's journey passes through $$$N$$$ locations numbered from $$$1$$$ to $$$N$$$. The distance between the $$$(i-1)$$$th and $$$i$$$th location is $$$A_i$$$.

Additionally, there are $$$M$$$ types of roads. The roads of the $$$k$$$th type are described with $$$3$$$ integers, $$$S_k$$$, $$$E_k$$$, $$$L_k$$$. For any $$$(i,j)$$$ such that $$$S_k \leq i < j \leq E_k$$$ and $$$abs(j-i) \leq L_k$$$, there is a road of the $$$k$$$th type from city $$$i$$$ to city $$$j$$$. Notice that $$$i \lt j$$$ because ascending causes horrific symptoms from the curse of the Abyss.

Furthermore, the cost of traversing the road from city $$$i$$$ to city $$$j$$$ is $$$(A_{i+1} \oplus A_{i+2} \oplus \dots \oplus A_j) - 16$$$ where $$$\oplus$$$ is the bitwise XOR operator.

A valid journey from city $$$1$$$ to $$$N$$$ satisfies that the types of the roads used are in $$$\textbf{strictly}$$$ increasing order. It is guaranteed that a valid journey exists.

Riko is an explorer, but she is not a programmer. So, Riko asks you to find the minimum cost for her to travel from city $$$1$$$ to city $$$N$$$.

The first line contains one integer, $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases. Then $$$T$$$ test cases follow.

The first line of each test case contains $$$2$$$ integers, $$$N$$$ and $$$M$$$ ($$$3 \leq N \leq 10^5$$$, $$$2 \leq M \leq 20$$$).

The second line of each test case contains $$$N-1$$$ integers: $$$A_2, A_3, \dots, A_N$$$ ($$$0 \leq A_i \leq 2^5-1$$$).

The last $$$M$$$ lines describe the roads. The $$$k$$$th of which contains $$$3$$$ integers, $$$S_k$$$, $$$E_k$$$, $$$L_k$$$ ($$$1 \leq S_k \lt E_k \leq N$$$, $$$1 \leq L_k \leq E_k-S_k$$$).

Tests $$$1-2$$$ will satisfy that the sum of $$$N^2$$$ over all test cases does not exceed $$$10^5$$$.

Tests $$$3-20$$$, the remaining tests, will satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

For each testcase, output the minimum cost for Riko to travel from city $$$1$$$ to city $$$N$$$.

1
4 2
1 1 2
1 3 2
1 4 2

-30

For the first and only test case of the example, there are $$$2$$$ possible ways to get from city $$$1$$$ to city $$$4$$$.

The first way: Take a road of type $$$1$$$ from city $$$1$$$ to city $$$2$$$, which costs $$$1 -16 = -15$$$. Then, take a road of type $$$2$$$ from city $$$2$$$ to city $$$4$$$, which costs $$$(1 \oplus 2) -16 = -13$$$. The total cost is $$$-15 + (-13) = -28$$$.

The second way: Take a road of type $$$1$$$ from city $$$1$$$ to city $$$3$$$, which costs $$$(1 \oplus 1) -16 = -16$$$. Then, take a road of type $$$2$$$ from city $$$3$$$ to city $$$4$$$, which costs $$$2 -16 = -14$$$. The total cost is $$$-16 + (-14) = -30$$$.

Thus, the minimum cost is $$$-30$$$.

$$$---------------------------------$$$

Idea: Codicon

Preparation: Codicon

Occurrences: Intermediate 11, Advanced 8