TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

85.5% (118/138)

Submission's AC Ratio

26.3% (213/809)

Tags

Description

從前的人常常由於林立的水泥建築而稱都市為水泥叢林,
但隨著時代的變遷,有的國際大都市擺脫了從前都市帶給人的灰濛濛的印象,
進而取代的是以華麗的大片玻璃,反射光線、映照出天藍色的天空的大廈,也有以五彩繽紛的鮮豔色彩彩妝的大樓。

Prinkskatcv 市就是大家口中的「現代都市」的最佳範本。
在 Prinkskatcv 的區域範圍內,你看不到傳統帶給人壓迫感的水泥建築,
取而代之的是整體感十足、縱使走在高樓大廈之間也不會感受到其壓力的現代建築,
當然,這些現代建築也非常的環保,詳細情形限於篇幅就不多說了。

現在,有一位知名的攝影家得知了這座優美的現代城市,因此想要前往 Prinkskatcv 市中最著名的 Kosivli St. 拍幾張照片放到所屬的著名攝影雜誌上,
但由於 Kosivli St. 的高樓大廈太多了,共有 $N$ 棟,不可能完全容納在一張照片內,
而且每棟大廈都有其獨特的特色,讓這位攝影師一時無法決定要使用哪張照片作為雜誌封面;
除此之外,也不是每張照片都可以被拿來作為封面的,作為封面的照片,該照片包含的景物不能太空曠也不能太稠密。
因此,這位攝影師經過了一番思考決定挑選出符合「照片中最高與最低的高樓大廈差正好為 $K$ 公尺」這項條件的照片,
但是還是有太多種可能的拍攝地點了,即使有了篩選照片的條件,也無法一下子就知道符合條件的拍攝位置在哪裡...

現在,這位攝影師想要請你幫個忙,希望你能幫他找出所有符合條件的拍攝位置。

為了簡化問題,你可以假設 Prinkskatcv 市內的高樓大廈每棟的寬度都相同且之間的距離都是可以被忽略的,
在此假設下,這位攝影師的相機鏡頭一次可以容納 $M$ 棟高樓大廈的寬度在範圍內(但是在街道的兩端則可能拍2≦$M'$≦$M$棟建築)。

此外,你可以認定 Kosivli St.上的所有建築物是只有單側且排成一直線的。

Input Format

每筆測試資料的第一行有三個正整數 N, M, K (2≦N≦107, 2≦M≦106, 1≦K≦231) ,

第二行有 N 個正整數 Hi (1≦H_i≦231, 1≦i≦N) 代表 Kosivli St.上由左到右第 i 棟建築(編號為 i)的高度(單位: 公尺)。

Output Format

請輸出所有符合條件的拍攝地點(範圍):

第一行請先輸出共有幾組符合條件的拍攝區間,
接下來每一行輸出一對正整數 L, R (1≦L≦R≦N) 表示編號 L 到編號 R 這段連續區間內的大樓符合條件,
若有多對解,則以 L 較小的先輸出;L 又一樣的話,以 R 較小的先輸出

其中由於照片中至少要有兩棟大樓,故 R-L≧1。

Sample Input 1

8 3 4
5 7 3 1 9 7 10 11

Sample Output 1

2
1 3
6 8

Hints

Scoring:
對於20%的測試資料,N≦2000
對於50%的測試資料,N≦500000

Problem Source

原TIOJ1566 / 第二屆快樂暑假營 -- 最終練習比賽
Problem Setter: Skyly

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1
1 3000 262144 262144 2
2 3000 262144 262144 3
3 3000 262144 262144 4
4 3000 262144 262144 5
5 6000 262144 262144 6
6 12000 262144 262144 7
7 30000 262144 262144 8
8 30000 262144 262144 9
9 3000 262144 262144 10