All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Making chocolate cakes
/
No tags
Problem
Editorial
Analytics

Lihas is a foodie. His love for food is never ending, nor is his love for chocolates. Today, his mother decides to make chocolate cake for him.

There are M ingredients needed for the cake and there are N containers for each ingredient, i.e. container Cm,n contains the amount of ingredient m in container n.

Also, each container has a capacity Km,n which denotes the maximum capacity which can come in a container. If more amount of that ingredient is added, the container will overflow and the extra capacity will flow out. Also, you need to make sure that the amount of ingredient in any container does not go below zero.

Now Lihas's mother uses contiguous containers of each type. For instance, to make the cake, if she uses the segment of containers from index L to R, then the total cake she can make for Lihas is:

CAKE = mini=1..M (sumj=L..R (Ci,j))

That is, the amount of cake made if Lihas's mother uses the segment of containers from L to R is the minimum of (sum of amount of ingredient from container L to R) for each container.

There are 2 types of queries:

Type 1: In the first type of query, there are three numbers X, Y and Z. In this type of query, you add Z to the container Cx,y. Keep in mind the capacity of this container should neither go below zero nor above it's limit Kx, y.

Type 2: In this query, you will be given two indices L and R, and you need to find the amount of cake Lihas's mother can make using all ingredients in containers from index L to R inclusive, 1 based indexing.

INPUT

The first line of input will contain 3 integers M, N and Q, the number of ingredients, the number of containers for each ingredient, and the number of queries.

The next M lines contains in each line N integers, the capacities of container n of ingredient m, i.e. Km, n.

The next M lines contains in each line N integers, the initial capacities of container n of ingredient m, i.e. Vm, n.

The next Q lines contain an integer 1 or 2, the type of query.

If the query is of type 1, you will get 3 integers X, Y and Z.

If the query is of type 2. you will get 2 integers L and R

1 <= M <= 10

1 <= N <= 100000

1 <= Q <= 100000

1 <= Km, n <= 1000000

1 <= Vm, n <= Km, n

1 <= X <= M

1 <= Y <= N

-1000000 <= Z <= 1000000

1 <= L <= R <= N

OUTPUT

For each query of type 2, you need to print the amount of cake Lihas's mother can make for him.

SCORING

Scoring will be as follows:

Score = (1 - c / 2500) * 250, where c is the number of characters in your code. In case the characters exceed 2500, your score will be zero.

SAMPLE INPUT
3 4 8
50 50 50 50
50 50 50 50
50 50 50 50
48 10 13 34
17 15 14 50
50 4 28 13
1 2 2 45
2 1 4
1 1 1 -15
2 1 4
1 3 4 40
2 1 4
1 1 2 40
2 1 4
SAMPLE OUTPUT
95
90
90
130
Explanation

You are given 3 ingredients, with 4 containers for each ingredient, with each container for each of the ingredient having limit of 50.

In the first query, the amount of second ingredient in the second container increases by 45. But since new value is greater than the limit, i.e. 50, extra overflows and the amount in the container is 50.

The quantity of ingredients in the containers after the update are (space separated 1-indexed):

Ingredient 1: 48 10 13 34

Ingredient 2: 17 50 14 50

Ingredient 3: 50 4 28 13

The second query asks for the cake Lihas's mother can make with all ingredients from index 1 to 4, i.e using all the containers for each ingredient. The total sum of ingredients from index 1 to 4 is:

Ingredient 1: 105

Ingredient 2: 131

Ingredient 3: 95

The minimum amount of ingredient is ingredient 3, which is 95 units. Therefore Lihas's mother can make 95 units of cake from all ingredients with container indices 1 to 4.

The third query reduces the quantity by 15 of ingredient 1 in container 1.

The fourth query is similar to the second query.

The fifth query adds 40 units of ingredient 3 to its corresponding container 4. But since the initial quantity was 13, new quantity is 53 and capacity is 50, some of it overflows for the final quantity to be 50. The quantities in the containers now are:

Ingredient 1: 33 10 13 34

Ingredient 2: 17 50 14 50

Ingredient 3: 50 4 28 50

Time Limit: 2.535 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?