i233. 加法搶答賽 - 高中生程式解題系統

內容

臨末之頌是一位電神，在 CF 上有著耀眼橘色的 rating，同時還是 TOI 2! 的國手。他喜歡裝弱，但是裝弱的時候還是揍爛窩，linlinorz。

你身為這位電神的同學，自然是羨慕不已。

今天 ricky 佬師(同樣是位電神，同樣喜歡裝弱，同樣比我電)在班上舉辦了一個搶答賽，規則如下：

給你一個數列 $a_{1}, a_{2}, \dots, a_{n}$ ，接下來會有 $q$ 筆詢問

每筆詢問包含兩個數字 $L, R$ ，請你計算

$\sum_{i = L}^{R} a_{i} \cdot (R - i + 1)$

簡單來說，對於 $L = 3, R = 5$ 就是要求 $a_{3} \cdot 3 + a_{4} \cdot 2 + a_{5} \cdot 1$

輸入說明

第一行為一個整數 $n$

第二行有 $n$ 個整數 $a_{1}, a_{2}, \dots, a_{n}$

第三行為一個整數 $q$ ，代表接下來有 $q$ 筆詢問

接下來 $q$ 行每行兩個整數 $L, R$

$1 \leq n \leq 10^{6}$

$| a_{i} | \leq 10^{6}$

$1 \leq q \leq 10^{6}$

$1 \leq L \leq R \leq n$

輸出說明

輸出 $q$ 行，回答每筆詢問後換行

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 3.0s , <50M
公開測資點#1 (10%): 3.0s , <50M
公開測資點#2 (10%): 3.0s , <50M
公開測資點#3 (10%): 3.0s , <50M
公開測資點#4 (10%): 3.0s , <50M
公開測資點#5 (10%): 3.0s , <50M
公開測資點#6 (10%): 3.0s , <50M
公開測資點#7 (10%): 3.0s , <50M
公開測資點#8 (10%): 3.0s , <50M
公開測資點#9 (10%): 3.0s , <50M

提示：

算法對了不優化IO也能過

2023/07/05 update：由於 zerojudge 系統變慢 (之前跑 0.7s 的 code 現在跑 1.4s)，時限放寬至 3s。

標籤:

臨末大電神

出處:

[管理者： fire5386 (becaidorz) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」