從前的人常常由於林立的水泥建築而稱都市為水泥叢林,
但隨著時代的變遷,有的國際大都市擺脫了從前都市帶給人的灰濛濛的印象,
進而取代的是以華麗的大片玻璃,反射光線、映照出天藍色的天空的大廈,也有以五彩繽紛的鮮豔色彩彩妝的大樓。
Prinkskatcv 市就是大家口中的「現代都市」的最佳範本。
在 Prinkskatcv 的區域範圍內,你看不到傳統帶給人壓迫感的水泥建築,
取而代之的是整體感十足、縱使走在高樓大廈之間也不會感受到其壓力的現代建築,
當然,這些現代建築也非常的環保,詳細情形限於篇幅就不多說了。
現在,有一位知名的攝影家得知了這座優美的現代城市,因此想要前往 Prinkskatcv 市中最著名的 Kosivli St. 拍幾張照片放到所屬的著名攝影雜誌上,
但由於 Kosivli St. 的高樓大廈太多了,共有 $N$ 棟,不可能完全容納在一張照片內,
而且每棟大廈都有其獨特的特色,讓這位攝影師一時無法決定要使用哪張照片作為雜誌封面;
除此之外,也不是每張照片都可以被拿來作為封面的,作為封面的照片,該照片包含的景物不能太空曠也不能太稠密。
因此,這位攝影師經過了一番思考決定挑選出符合「照片中最高與最低的高樓大廈差正好為 $K$ 公尺」這項條件的照片,
但是還是有太多種可能的拍攝地點了,即使有了篩選照片的條件,也無法一下子就知道符合條件的拍攝位置在哪裡...
現在,這位攝影師想要請你幫個忙,希望你能幫他找出所有符合條件的拍攝位置。
為了簡化問題,你可以假設 Prinkskatcv 市內的高樓大廈每棟的寬度都相同且之間的距離都是可以被忽略的,
在此假設下,這位攝影師的相機鏡頭一次可以容納 $M$ 棟高樓大廈的寬度在範圍內(但是在街道的兩端則可能拍2≦$M'$≦$M$棟建築)。
此外,你可以認定 Kosivli St.上的所有建築物是只有單側且排成一直線的。
每筆測試資料的第一行有三個正整數 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)的高度(單位: 公尺)。
請輸出所有符合條件的拍攝地點(範圍):
第一行請先輸出共有幾組符合條件的拍攝區間,
接下來每一行輸出一對正整數 L, R (1≦L≦R≦N) 表示編號 L 到編號 R 這段連續區間內的大樓符合條件,
若有多對解,則以 L 較小的先輸出;L 又一樣的話,以 R 較小的先輸出
其中由於照片中至少要有兩棟大樓,故 R-L≧1。
Scoring:
對於20%的測試資料,N≦2000
對於50%的測試資料,N≦500000
原TIOJ1566 / 第二屆快樂暑假營 -- 最終練習比賽
Problem Setter: Skyly
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 |