Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

No Onion, No Cry

By Hasinur_ · Limits 1s, 512 MB

-Onions make us cry, don’t they? They can make us happy too.


-Read the statement carefully!

Scientist Dr. Shiku has created genetically modified Onions in his laboratory. Each day he tries to create new types of onions and preserves them. Onions created in each day are preserved in a new jar. This jar has two values (O,H) associated with it. This pair of values (O,H) is called the ‘O-Pair’ of this jar.

O = Number of onions in it.
H = Happiness value.

You can increase or decrease the number of onions O by the happiness value H. That means (O,H) can be transformed into (O’,H’) = (O + H , H ) or ( O - H , H ) when H<=O.
You can increase or decrease the Happiness value H by the number of Onions O. That means (O,H) can be transformed into (O’,H’) = (O, H + O ) or ( O , H - O ) when O<=H.

If there are Jars that can reach the same ‘O-pair’ by performing the above operation any number of times they are considered ‘Same Group’. Now make an array of happiness values from a ‘Same Group’. ‘Ultimate Happiness value’ for each group is defined as the sum of the product of each subset of the array.

For example (1,3),(1,4),(1,3) are the O-Pairs of the same group. Now let’s make an array by taking the happiness values of the jars of this same group. The array is [ 3 , 4 , 3 ]. So, the ultimate happiness value of this group is 3 + 4 + 3 + 3*4 + 4*3 + 3*3 + 3*4*3 = 79.

You are the assistant of the great scientist Dr. Shiku. He asked you to write a program that will help him to take the research far. Each day Dr. Shiku needs the program to perform three kinds of queries:

Type 1: pair of integers (O,H) will be given. The program has to store information about the new jar that is created today.
Type 2: An integer P will be given. The lab will now contain only the jars which were there on the Pth day.

To understand the Type 2 query: Let Dr Shiku had jars of O-pairs (1,3), (1,4) on the second day and he created a new jar of O-pair (1,6) on the third day. So, on the third day, he has jars of (1,3), (1,4) and (1,6). If Dr. Shiku asks you to perform a query of type 2 where P = 2 on the fourth day then Dr. Shiku will only have the jars of the second day. That means on the fourth day Dr. Shiku has the jars of O-pairs (1,3) and (1,4) that were on the second day.

Type 3: An integer V will be given. You have to smile and print the sum of the ‘Ultimate Happiness Value’ of the groups formed by the Onion jars in the lab that can reach (O’,H’)<=(V,V).
(O,H) is less than or equal to (V,V) when O’<=V and H’<=V.

Counting large values for query type 3 is the ultimate happiness for you. Please smile! :D


First line of the input will contain an integer D. Number of days. On each day you will be given any one of the queries:
1 O H
or, 2 P
or, 3 V

First integer of each query represents the query type described in the description.

1 <= D <= 105
1 <= O,H <= 106
1 <= P <= Number of days till now - 1
1 <= V <= 106


For each query of type 3 print “Day #x: y” where x is number of the day and y is required answer modulo 109 + 7.


1 2 2
1 1 3
1 1 4
1 1 3
3 1
3 2
3 5
2 3
3 1
3 2
Day #5: 79
Day #6: 81
Day #7: 81
Day #9: 19
Day #10: 21


33% Solution Ratio

mahdi.hasnatEarliest, 4w ago

mahdi.hasnatFastest, 0.1s

mahdi.hasnatLightest, 132 MB

mahdi.hasnatShortest, 3166B


Login to submit