DCEPC206 - Its a Murder!

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

hide comments
r_avvaru: 2021-05-23 11:41:22

I used merge sort but don't understand y it is failing on hidden test cases

Last edit: 2021-05-23 11:42:05
abhishen99: 2020-11-04 12:49:45

good problem simple bit

silent_1: 2020-06-12 16:36:51

Similar Problems

scolar_fuad: 2019-11-10 15:04:25

what a nice problem !
I Solved this using merge sort
Time : 0.05s
is there any idea to you share with me

tanmay2904: 2019-09-28 14:07:51

Got AC using simple BIT, without any coordinate compression.
All those getting TLE check for 0 input.

prudhvi_495: 2019-06-17 20:44:40

Same as "count inversion problem"
My 150th :)

Last edit: 2019-06-17 20:45:01
exesharkx: 2019-04-05 22:19:37

Coordinate Compression + BIT

chop_top: 2019-01-07 06:40:05

If you use BIT then use coordinate compression, otherwise you'll get TLE.

eagleshadow: 2018-09-27 20:08:13

AC in one go :)

karan_yadav: 2018-08-10 21:09:49

Merge sort - 0.07s
BIT (Naive) - TLE
BIT (optimised) - 0.09s
All the solutions are using slow I/P ie, cin, cout - without ios::sync_with_stdio(false)

Last edit: 2018-08-11 09:18:55

Added by:dce coders
Time limit:1.259s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem