Submit | All submissions | Best solutions | Back to list |
Problem hidden
LIFERACE - LIFE IS A RACE |
Life is a race with hard working humans. Assume a hypothetical situation in which God has to send many humans on earth with some level of intelligence. Level of intelligence is measured in a whole number. God has to take care that person arriving later on earth should have more level of intelligence so as to cope with the competitive world. God’s assistant suggested him a non-decreasing sequence called S. Lets see the sequence.
Description of Sequence
Any natural number n occurs exactly S[n] times and all n occurs consecutively. The first few terms are stated below.
n 1 2 3 4 5 6 7 8 9 10 11 12 ...
S(n) 1 2 2 3 3 4 4 4 5 5 5 6 ...
S[1000] = 86
So, Person 1 arrives on earth with level of intelligence = 1.
Person 2 arrives on earth with level of intelligence = 2.
Person 3 arrives on earth with level of intelligence = 2.
Person 4 arrives on earth with level of intelligence = 3.
And so on.
But God sends some good hearted person (Person who not only lives for themselves but for the world) when n's cube root is a positive integer. But there is a SuperGod which rarely opens his eyes and as he opens his eyes, he increases the level of intelligence of some of the good hearted persons. Now God needs to know the total level of intelligence of some of the good hearted people.
Good hearted person 1: person 1
Good hearted person 2: person 8
Good hearted person 3: person 27
Good hearted person 4: person 64
And so on.
God needs a programmer to solve his queries. God’s input data format is explained below.
Will You help God?? (He might increase your lifetime :) )
Input
First line of input contains 2 integers, x and y, where x denotes the number of time the SuperGod opened his eyes and y denotes the number of queries of God.
Next x lines follows 3 integers L, R, I, which denote that SuperGod has increased the level of intelligence of good hearted people ranging between L and R (inclusive both) by a constant I.
Next y lines follows 2 integers L, R, which denotes that God needs to know the total level of intelligence of good hearted persons ranging between L and R (both inclusive).
Note:
Good hearted person L is person L*L*L.
Good hearted person L+1 is person (L+1)*(L+1)*(L+1)
Good hearted person R is person R*R*R.
Output
Output should contain exactly y lines, each containing the answer.
Example
Input: 1 1 1 1 1 1 2 Output: 6
Explanation of Example
Answer is S[1] + S[2*2*2] + 1 = 6
Constraints
x <= 100000
y <= 100000
1 <= L, R <= 999999
I <= 10
Added by: | devu |
Date: | 2013-03-18 |
Time limit: | 1s |
Source limit: | 5000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem. |