Joker and the Arkham Asylum
All submissions for this problem are available.
The Arkham Asylum of Gotham, is the place of residence of evils. Batman uses his super awesome Bat-Technology to guard it against the potential outbreak.
The Asylum can be considered as a NxN maze, where each cell houses a building. Note that, the left most building in the bottom most row is said to be present at the cell in 1st row and 1st column. Similarly, the right most building in the top most row is said to be present at the cell in Nth row and Nth column. Each building is pyramidal in shape and is three storey high.
Once a while, Batman catches prisoners and puts them into Arkham Asylum. Note that, initially, the Asylum is empty. For proper utilization of pyramidal space, the distribution of new prisoners in a building is as follows:
If D+D2+D3 new prisoners are inserted in a building, D3 goes into ground floor, D2 into first floor and D into second floor.
Now, Batman places the new prisoners in the buildings along a tilted line, 45° to the sides of the maze, in the increasing direction of row numbers.
Note that, he could start this line anywhere in the first row. He would place (D+D2+D3) prisoners in each building, in above described manner.Also, it is guaranteed that the number of new prisoners would be a multiple of D+D2+D3 and this line would atmost reach the boundary of the maze, i.e Batman would start this line well in advance, so as to accommodate all prisoners.
Under the effect of the super awesome Bat-Technology, the power packets required to escape from the Asylum, for each prisoner living in the building at jth row and
ith column of the maze is given by:
- F0 (i,j) = (j-1)3 for the ground floor
- F1 (i,j) = (j-1)2 for the first floor
- F2 (i,j) = (j-1) for the second floor
Note that the super awesome Bat-Technology is super-costly (even for Batman!) and is employed just inside the Asylum and nowhere else outside it. So, the prisoners are free to move anywhere once they are outside the prison.
Now the Joker, who enjoys chaos, decides to free some prisoners. For that, he needs some power packets, which he can smuggle into the Asylum and distribute it amongst prisoners so as they can be free and join with him in his quest for establishing the reign of Chaos in the universe.
The Joker needs your help to find out the number of power packets needed to free the prisoners from all the building in between and including columns X and Y, in all rows. Since the answer could be very, very large (after all, you are fighting against the super awesome Bat-Technology), you need to print your answer modulus 109+7.
- First Line contains 2 space separated Integers N and T, denoting the size of the maze and the number of queries to follow.
- Next T lines follow which will either be of form (U X Y D) OR (Q X Y) without brackets.
U X Y D denotes the addition of (Y-X+1)*(D+D2+D3) prisoners, in a line starting from the Xth building in first row and extending upto Yth building in (Y-X+1)th row,
Q X Y denotes that Joker wishes to query the cost of releasing the prisoners in the above described manner.
- For each Query of type Q output a single line containing the answer as required.
- 1 ≤ N ≤ 105
- 1 ≤ T ≤ 105
- 1 ≤ X ≤ Y ≤ N
- 1 ≤ D ≤ 100
U 1 4 2
Q 2 3
After the first update, the Asylum looks like this:
0,0,0 0,0,0 0,0,0 8,4,2
0,0,0 0,0,0 8,4,2 0,0,0
0,0,0 8,4,2 0,0,0 0,0,0
8,4,2 0,0,0 0,0,0 0,0,0
Here, each tuple (a,b,c) denotes the current number of persons in the building, in ground floor, first floor and second floor respectively.
The answer is (8*1+4*1+2*1)+(8*8+4*4+2*2) = 14+84 = 98
|Time Limit:||2 - 3 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.