TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

33.8% (47/139)

Tags

Description

Dice Wars是一款兼具謀略和運氣的遊戲。

遊戲中你扮演紫色的骰子,要攻下其他顏色的骰子的城池,進而統一全地圖。

如今你選到了一張看起來不錯的地圖--整張地圖呈一條直線,每個位置都有一個顏色勢力佔領。

由於每次移動到相鄰異色的城池都必須經歷一場鏖戰,你想先經過程式計算後再進行遊戲。

你想要每次詢問一個顏色對(S, T),問從任何一個S的城池到任一個T的城池至少要經過幾場戰鬥。

如果S或T已經滅亡(地圖中沒有任何一個該勢力),就輸出-1。

Input Format

輸入第一行有兩個數字N, M。表示地圖共有N格、接下來有M個詢問。

接下來一行有N個以空白隔開的數字Ci表示佔領第i個位置的顏色勢力。

接下來會有M行,每行兩個正整數S, T,表示每次詢問。

1 <= N, M <= 60000
1 <= Ci, S, T <= N

Output Format

輸出會有M行,每行包含一個整數Ai表示對第i個詢問的回答。

Sample Input

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

Sample Output

1
3
0
-1

Hints

第一個詢問是問從勢力1到勢力2要經過幾次戰鬥。
最近的就是從位置3的勢力1到位置2的勢力2,經過1場戰鬥(打下位置2)

第二個詢問是問從1到3要經過幾次戰鬥。
最近的就是從位置4的勢力1到位置7的勢力3,經過3場戰鬥(打下位置5、6、7)

第三個詢問是問從1到1要經過幾次戰鬥。
所以是0場。

第四個詢問中,因為地圖上沒有4所以輸出-1。

Problem Source

原TIOJ1726 / Problem Setter : ATP

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536
7 3000 65536
8 3000 65536
9 3000 65536