PAIRSUM - Sum of Pairwise Products
Given N non negative numbers, the task is to answer M queries.
Each query is as follows:
Given u,v you need to find the pairwise product sum (u and v are zero indexed)
auau + au+1au+1 + au+1au + au+2au+2 + au+2au+1 + au+2au + ... + avav + avav-1 + ... + avau
Input
N a0 a1 ... aN-1 M u1 v1 u2 v2 ... uM vM
Output
Print the answer for each query in a separate line.
Example
Input: 5 2 0 1 3 3 3 0 2 1 2 3 4 Output: 7 1 27
Constraints
0 <= u <= v < N
N <= 100000
M <= 100000
0 <= ai <= 1000000
hide comments
Pranjal Successena:
2013-03-07 16:34:04
can u give more test cases.
|
|
Pranjal Successena:
2013-03-07 16:34:01
can u give more test cases.
|
|
BOND:
2012-08-25 06:21:36
ohh man, i am really bad at type conversions... two WA's after AC :( |
|
Kiran Danduprolu:
2011-10-05 22:07:36
Nice problem ... had fun solving it |
|
:D:
2011-09-21 08:48:00
Unsigned long long should be enough to hold final and intermediate results. |
Added by: | Manukranth |
Date: | 2011-09-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |