TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

55.6% (10/18)

Submission's AC Ratio

17.0% (23/135)

Description

給你一個整數數列$a_0,a_1,\cdots ,a_{N-1}$。接下來給定很多組詢問$(l,r)$(保證$0\leq l<r\leq N$),請你計算出$\prod_{i=l} ^ {r-1} a_i= a_l\times a_{l+1}\times\cdots\times a_{r-1}$的近似值。

注意:由於本題輸入/輸出十分龐大,使用C++作答的同學,請在程式碼開頭加上#include <cstdio>,並利用scanf讀入資料、用printf輸出資料
scanfprintf的使用方式在下方Hints中有陳述。

Input Format

第一行包含兩個正整數$N,Q$,以空白隔開,分別代表數列的長度和詢問的總數。
接下來有一行包含$N$個以空白隔開的整數$a_0,a_1,\cdots ,a_{N-1}$。
接下來$Q$行,每行有兩個非負整數$l,r$,代表一組詢問。

對於所有測資,$N,Q\leq 3\times 10^ 6; |a_i|\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0,5) $N \leq 4, Q \leq 400$ 6
2 (0,1,5,6) $N \leq 30, Q \leq 1000$ 30
3 (0~2,5~7) $N \leq 400, Q \leq 1000$ 22
4 (0~3,5~8) $N, Q \leq 10^ 4$ 12
5 (0~9) 無額外限制 30

Output Format

對於每組詢問請輸出一行包含一個數字,代表題目要求的答案。你可以用正常的數字或科學記號表示法輸出(見範例輸出)。
對於每一筆詢問,若你的答案和正確答案相對或絕對誤差其中一者不超過$10^ {-7}$,就會被視為正確。

Sample Input

5 5
1 2 3 4 5
0 5
1 3
3 5
0 1
1 4

Sample Output

120
6.0000000000000100000
2e+1
1.00E+000
+24.00

Hints

scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。

printf 常用的輸出方式如下:
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。
printf("%.5f\n",x); 輸出一行包含一個double 型態變數x到小數點後5位(可自行將5換成其他正整數)。
printf("%.5Lf\n",y); 輸出一行包含一個long double 型態變數y到小數點後5位(可自行將5換成其他正整數)。
printf("%.5e\n",x); 以科學記號表示法輸出一行包含一個double 型態變數x,尾數輸出到小數點後5位(可自行將5換成其他正整數)。
printf("%.5Le\n",y); 以科學記號表示法輸出一行包含一個long double 型態變數y,尾數輸出到小數點後5位(可自行將5換成其他正整數)。

Problem Source

Problem set by Yihda Yol
建國中學107學年度校隊選拔:初試pE

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 0 ~ 1, Score: 15
For Testdata: 0 ~ 2, Score: 11
For Testdata: 0 ~ 3, Score: 6
For Testdata: 0 ~ 4, Score: 15
For Testdata: 5 ~ 5, Score: 3
For Testdata: 5 ~ 6, Score: 15
For Testdata: 5 ~ 7, Score: 11
For Testdata: 5 ~ 8, Score: 6
For Testdata: 0 ~ 9, Score: 15
No. Time Limit (ms) Memory Limit (KiB)
0 1500 131072
1 1500 131072
2 1500 131072
3 1500 131072
4 7500 131072
5 1500 131072
6 1500 131072
7 1500 131072
8 1500 131072
9 7500 131072