修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm
Submit Ranklist
Problem : 263 - Elephants
Problem Statistics
Solved Member: 6 Submission: 52 User Tried: 7Statement:
在芭堤雅，大象跳舞(Dancing Elephants)是一個壯觀的表演，它有N 隻大象排成一條線(稱為舞台)跳舞。
經過多年訓練，大象能表演許多驚人的舞蹈。這個表演是由一系列的曲目(act)組成，每一曲目由一隻大象表演一段可愛的舞蹈，同時該大象可能會變換位置。
這個表演的製作人想要出一本內有完整表演照片的相簿，每表演完一個曲目，他們想要對所有被觀眾看到的大象拍照。
表演進行時，多隻大象可能會站在同一位置，在那種情況下，這些大象會一隻隻按前後方式排列。
一群大象可以用一台相機來拍照，若且為若(if and only if)這群大象位於長度為L 的線段上(含線段的兩個端點)。因為大象可以散開在舞台上，因此可能需要多台相機才能同時拍到所有大象。
舉例來說，假設L=10，而且大象站在舞台上10, 15, 17, 和20 的位置，此時，一台相機就足以拍照，如下圖所示(三角形代表大象、梯形代表相機)。
下一曲目，位置15 的大象跳舞移位到位置32；表演完這個曲目後，我們需要至少二台相機來拍照，如下圖所示。
下一曲目，位置10 的大象移到位置7；在這個曲目後，我們需要至少三台相機來對所有大象拍照，如下圖所示。
你必須決定每表演完一個曲目後，最少需用幾台相機拍照。注意：每表演完一個曲目後，相機的數目可能會增加、減少或維持不變。
經過多年訓練，大象能表演許多驚人的舞蹈。這個表演是由一系列的曲目(act)組成，每一曲目由一隻大象表演一段可愛的舞蹈，同時該大象可能會變換位置。
這個表演的製作人想要出一本內有完整表演照片的相簿，每表演完一個曲目，他們想要對所有被觀眾看到的大象拍照。
表演進行時，多隻大象可能會站在同一位置，在那種情況下，這些大象會一隻隻按前後方式排列。
一群大象可以用一台相機來拍照，若且為若(if and only if)這群大象位於長度為L 的線段上(含線段的兩個端點)。因為大象可以散開在舞台上，因此可能需要多台相機才能同時拍到所有大象。
舉例來說，假設L=10，而且大象站在舞台上10, 15, 17, 和20 的位置，此時，一台相機就足以拍照，如下圖所示(三角形代表大象、梯形代表相機)。
下一曲目，位置15 的大象跳舞移位到位置32；表演完這個曲目後，我們需要至少二台相機來拍照，如下圖所示。
下一曲目，位置10 的大象移到位置7；在這個曲目後，我們需要至少三台相機來對所有大象拍照，如下圖所示。
你必須決定每表演完一個曲目後，最少需用幾台相機拍照。注意：每表演完一個曲目後，相機的數目可能會增加、減少或維持不變。
Input:Output:
第一行有三個以空白隔開的整數 N, L, M，大象編號從0 到N-1，L為一台相機所能捕捉的線段長度，你可以假設L 是一個整數，並且滿足0 ≤ L ≤ 1 000 000 000， M 是表演中的曲目數量。
接下來有 N 行，第 i 行為編號 i-2 的大象的位置值X[i]，你可以假設0 ≤ X[0] ≤ ... ≤ X[N-1] ≤ 1000000000。注意：大象的順序於跳舞中可能會重排。。
然後是 M 行，每行兩個數字a, b，表示編號a的大象表演完後移動到位置b，滿足0 ≤ b ≤ 1 000 000 000。
為了讓題目有點現場感，所以HH決定在輸入上做點小魔術。
對於輸入的a, b其實不是真正的a, b，你必須減去前一個輸出的數字才會得到真正的a, b，若之前還未輸出任何數字則無視此規則。
例如：假設第 i 個表演結束後你輸出 s[i]，那麼在第 i+1 個表演輸入的a, b都減去 s[i] 才會得到真正的a, b( 即 a-s[i] 與 b-s[i] )。
Subtask 1 (10 points)
•恰好有 N = 2 隻大象，M ≤ 100。
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 2 (16 points)
•1 ≤ N, M ≤ 100。
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 3 (24 points)
•1 ≤ N, M ≤ 50 000.
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 4 (47 points)
•1 ≤ N, M ≤ 70 000.
•大象可能共用同一位置。
Subtask 5 (3 points)
•1 ≤ N, M ≤ 150 000.
•大象可能共用同一位置。
由於judge時間非常長，因此Subtask 5只抓了兩筆。
接下來有 N 行，第 i 行為編號 i-2 的大象的位置值X[i]，你可以假設0 ≤ X[0] ≤ ... ≤ X[N-1] ≤ 1000000000。注意：大象的順序於跳舞中可能會重排。。
然後是 M 行，每行兩個數字a, b，表示編號a的大象表演完後移動到位置b，滿足0 ≤ b ≤ 1 000 000 000。
為了讓題目有點現場感，所以HH決定在輸入上做點小魔術。
對於輸入的a, b其實不是真正的a, b，你必須減去前一個輸出的數字才會得到真正的a, b，若之前還未輸出任何數字則無視此規則。
例如：假設第 i 個表演結束後你輸出 s[i]，那麼在第 i+1 個表演輸入的a, b都減去 s[i] 才會得到真正的a, b( 即 a-s[i] 與 b-s[i] )。
Subtask 1 (10 points)
•恰好有 N = 2 隻大象，M ≤ 100。
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 2 (16 points)
•1 ≤ N, M ≤ 100。
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 3 (24 points)
•1 ≤ N, M ≤ 50 000.
•一開始以及每個曲目後，所有大象的位置皆不同。
Subtask 4 (47 points)
•1 ≤ N, M ≤ 70 000.
•大象可能共用同一位置。
Subtask 5 (3 points)
•1 ≤ N, M ≤ 150 000.
•大象可能共用同一位置。
由於judge時間非常長，因此Subtask 5只抓了兩筆。
一共輸出 M 行，第 i 行的數字表示第 i 個表演結束後所需的最少相機數量。
Sample Input:Sample Output:
4 10 5
10
15
17
20
2 16
2 26
5 37
2 40
4 2
10
15
17
20
2 16
2 26
5 37
2 40
4 2
1
2
2
2
3
2
2
2
3
HINT:
Sample輸入其實長這樣：
4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0
4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0
Source:
IOI 2011Problem Setter
hanhan0912Testdata:
| Test | Time | Memory | Score |
|---|---|---|---|
| 0 | 1000ms | 262144kb | |
| 1-1 | 1000ms | 262144kb | 10 |
| 1-2 | 1000ms | 262144kb | |
| 1-3 | 1000ms | 262144kb | |
| 2-1 | 1000ms | 262144kb | 16 |
| 2-2 | 1000ms | 262144kb | |
| 2-3 | 1000ms | 262144kb | |
| 3-1 | 5000ms | 262144kb | 24 |
| 3-2 | 5000ms | 262144kb | |
| 3-3 | 5000ms | 262144kb | |
| 3-4 | 5000ms | 262144kb | |
| 3-5 | 5000ms | 262144kb | |
| 3-6 | 5000ms | 262144kb | |
| 3-7 | 5000ms | 262144kb | |
| 4-1 | 12000ms | 262144kb | 47 |
| 4-2 | 12000ms | 262144kb | |
| 4-3 | 12000ms | 262144kb | |
| 4-4 | 12000ms | 262144kb | |
| 4-5 | 12000ms | 262144kb | |
| 4-6 | 12000ms | 262144kb | |
| 4-7 | 12000ms | 262144kb | |
| 4-8 | 12000ms | 262144kb | |
| 4-9 | 12000ms | 262144kb | |
| 5-1 | 60000ms | 262144kb | 3 |
| 5-2 | 60000ms | 262144kb |
NeoHOJ — The new era of HOJ
頁面讀取時間: 0.0068 秒，使用記憶體: 0.46MB 。
GitHub