Daddy and Chocolates
All submissions for this problem are available.
Po - the Panda, is the chosen dragon warrior who is destined to bring peace in the universe. He fights evil Kung Fu Masters. He is amazingly witty, but wittier is his master, Master Shifu, who taught him the strongest move he knows, THE WUXI FINGER HOLD. But little does his master know that his skills are not the secret to his power, but chocolates, which his daddy makes for him.
But now, there is trouble in the paradise. Tai Lung has come to defeat the dragon warrior, and to prepare Po, his daddy needs chocolates. But unfortunately, the stock of ingredients to make the chocolates has finished. So daddy rushes to the market to buy the ingredients.
In the market, there is only one shop, and taking benefit of this thing, the shopkeeper charges hefty!
There are a total N ingredients in the shop, each with a cost Ci. There is an infinite supply of each ingredient in the shop. The battle will last D days, so each day, daddy buys a contiguous subset of the ingredients defined by index L and R(1 ≤ L ≤ R ≤ N). Daddy buys all ingredients, one each, from index L to R(inclusive).
Now the problem is the calculation of the total cost of the ingredients. The shopkeeper's formula for deciding the total cost of the ingredients is as follows:
Let there be K different ingredients with cost C, so the cost with the normal calculation for all these ingredients should be K*C, but according to the shopkeeper, the cost of these ingredients is K*K*C.
You need to find out the total cost for each day.
First line of the input will contain two integers N and D, the number of ingredients and the number of days respectively.
The second line will have N integers, Ci (1 ≤ i ≤ N), denoting the cost of element i.
The next D lines contain two integers L and R, denoting the contiguous array of ingredients daddy needs to buy on this day.
For each day, output a single line containing the total cost of the ingredients for that day.
- 1 ≤ N,D ≤ 200000
- 1 ≤ Ci ≤ 1000000
- 1 ≤ L ≤ R ≤ N
Input: 3 2 1 2 1 1 2 1 3 Output: 3 6
Input: 8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7 Output: 20 20 20
Example case 1.
The ingredients selected in range [1,3], i.e. day 2.
Total cost = 2*2*1 + 1*1*2 = 6
Example case 2.
Consider the following array, and the ingredients selected in range [2,7], i.e. day 1.
Total cost = 3*3*1 + 2*2*2 + 1*1*3 = 20
|Tags||dmnt2016, medium, mo-algorithm, sahilarora.535|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions