Sphere Online Judge

SPOJ Problem Set (classical)

10810. Its a Murder!

Problem code: DCEPC206

Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.


First line gives T, number of test cases.

2T lines follow.

First line gives you the number of stairs N

Next line gives you N numbers written on the stairs.


For each test case output one line giving the final sum for each test case.




All numbers will be between 0 and 10^6.


1 5 3 6 4

Output: 15

Added by:dce coders
Time limit:3s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Resource:Own Problem

hide comments
2014-07-01 08:47:35 785227
Beware of overflows. To avoid that, use long long throughout your code :)
2014-07-01 08:38:22 785227
Handle the overflows during multiplication. Lots of WAs because of that
2014-05-27 07:41:09 monera
My 50th :D
2014-01-05 20:50:02 Vipul Pandey
remember "sum of all the numbers previously seen on the stairs which are smaller than the present number" and not smaller or equal.Equal costed me a WA. But still it is a nice one!
2013-09-21 11:13:31 Ouditchya Sinha
A lot of server instability. Using unsigned long long is faster than long long. Can anyone explain please? :)
2013-08-02 10:19:28 Quantum
nice one...!!
2013-06-11 11:59:42 Abhinav Aggarwal
Nice question! :)
2013-04-16 18:51:28 Lakshay Singhal
getting NZEC....running well on ideone and other compiler
2013-04-01 09:46:13 Ivan Nikulin
I somehow managed to assume that all the numbers are different (: Therefore, HINT: numbers might NOT be DISTINCT!
2013-06-18 14:56:49 Pranshul Agarwal
Nice problem. Learnt a lot from this.. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.