| Submit | All submissions | Best solutions | Back to list |
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
| Added by: | Manukranth |
| Date: | 2011-09-20 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
hide comments
|
||||||
|
2017-08-06 10:52:03
Fast IO + O(1) query answers, still TLE in Python :( Edit Dec'2017: Surprised to find this problem in my AC list. Perhaps the TL has been tweaked and solutions rejudged. Last edit: 2017-12-31 03:37:44 |
||||||
|
2016-12-17 12:24:42
Same code:- Java - TLE C - AC :( |
||||||
|
2016-07-03 18:52:08
Use scanf and printf |
||||||
|
2016-05-22 10:14:08 hmp
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 |
||||||
|
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 |
||||||
|
2016-02-11 10:09:01 ayush sinha
recall 10 class maths |
||||||
|
2016-02-05 22:01:13
use scanf printf ,long long int,.O(n+m) possible with DP :) |
||||||
|
2015-03-06 18:20:24 Nikhil Sheoran
Even with O(M+N) requires fast i/o.. |
||||||
|
2015-01-07 09:00:34 Sudarshan K
Problem setter. Please move this to Cube Cluster. Can't submit in C/C++. Says Language available only on Cube Cluster. |
||||||
|
2014-07-10 17:29:30 AAKASH TYAGI
50th problem on spoj :) answer queries in constant time |
||||||
RSS