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
nadstratosfer:
2017-08-06 10:52:03
Fast IO + O(1) query answers, still TLE in Python :(
|
|
kira28:
2016-12-17 12:24:42
Same code:-
|
|
baadshah_:
2016-07-03 18:52:08
Use scanf and printf |
|
hmp:
2016-05-22 10:14:08
to avoid TLE for cin/cout not only use ios_base::sync_with_stdio(false); but also tie cin/cout; Last edit: 2016-05-30 03:57:57 |
|
deradler:
2016-05-20 22:19:45
gud ques, derived a general formula ((sum of nos in a range)^2 + sum of squares of numbers)/2. Last edit: 2016-05-20 23:15:19 |
|
ayush sinha:
2016-02-11 10:09:01
recall 10 class maths |
|
sarvesh_19:
2016-02-05 22:01:13
use scanf printf ,long long int,.O(n+m) possible with DP :) |
|
Nikhil Sheoran:
2015-03-06 18:20:24
Even with O(M+N) requires fast i/o.. |
|
Sudarshan K:
2015-01-07 09:00:34
Problem setter. Please move this to Cube Cluster. Can't submit in C/C++. Says Language available only on Cube Cluster. |
|
AAKASH TYAGI:
2014-07-10 17:29:30
50th problem on spoj :)
|
Added by: | Manukranth |
Date: | 2011-09-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |