TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

59.3% (32/54)

Submission's AC Ratio

14.1% (56/398)

Tags

Description

給你一個整數數列a0,a1,,aN1。接下來給定很多組詢問(l,r)(保證0l<rN),請你計算出i=lr1ai=al×al+1××ar1的近似值。

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

Input Format

第一行包含兩個正整數N,Q,以空白隔開,分別代表數列的長度和詢問的總數。
接下來有一行包含N個以空白隔開的整數a0,a1,,aN1
接下來Q行,每行有兩個非負整數l,r,代表一組詢問。

對於所有測資,N,Q3×106;|ai|109

子任務(測資) 額外限制 分數
1 (0,5) N4,Q400 6
2 (0,1,5,6) N30,Q1000 30
3 (0~2,5~7) N400,Q1000 22
4 (0~3,5~8) N,Q104 12
5 (0~9) 無額外限制 30

Output Format

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

Sample Input 1

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

Sample Output 1

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 131072 262144 1 2 3 4 5 10
1 1500 131072 262144 2 3 4 5 10
2 1500 131072 262144 3 4 5 10
3 1500 131072 262144 4 5 10
4 7500 131072 262144 5 10
5 1500 131072 262144 6 7 8 9 10
6 1500 131072 262144 7 8 9 10
7 1500 131072 262144 8 9 10
8 1500 131072 262144 9 10
9 7500 131072 262144 10