Art Academy IV: Alice's Blazing Fury

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 2.5s
Java 5.0s
Python 20.0s
Memory limit: 128M
Python 256M

Author:
Problem type

You notice a disturbance in the area. Something on this particular day is strangely, off?

Is it because hewmatt10 has been sabotaged?

Is it because both astrocat879 and skyflaren are nowhere to be found?

Simply put, it's much more frightening than that.

Today marks the end of an era. [REDACTED] has finally had enough of scandals like hewmatt10 being able to freely roam around her majestic Empire. To ensure that her task is as quick as possible, she will be activating her Empire's secret stash of illegal weaponry, which has been crafted with only one purpose in mind - destruction.

Since this is her Empire after all, the weapons have been specifically named after her - The Alicizer. [REDACTED] has not only one, not two, but an infinite stash of Alicizers, which she will be placing down at specific coordinates along her N row by M column Empire. The more in a line, either vertically or horizontally, there are, the more powerful and destructive they get. Since [REDACTED] is a cruel person by nature, she will be placing down Alicizers in large square-shaped chunks at a time.

Such a ruthless task will definitely face resistance, as hewmatt10 and his army will be tryharding epically to defend his basement art academy. hewmatt10's basement workers have engineered a special line of defense that they will be using to protect themselves, called the Anti-Alicizer. Just like how Alicizers will be placed in large square-shaped chunks at a time, an Anti-Alicizer will be able to remove square-shaped chunks of Alicizers.

As a spectator of this war, yeahbennou would rather not get completely obliterated in battle, and instead like to record down some statistics as the war goes on. Since he is lazy, yeahbennou wants you to create a program which will answer Q queries to help him keep track of the battle.

Input Specification

On the first line, there will be three space-separated integers - N, M (1 \le N \times M \le 5 \times 10^5), and Q (1 \le Q \le 5 \times 10^4), representing the size of [REDACTED]'s empire, and the number of queries yeahbennou wants you to perform.

The following Q lines will contain one of the following queries:

Format Description
1\ x\ y\ z At the position (x, y), place down Alicizers in a z by z square. (1 \le x \le N), (1 \le y \le M), (1 \le z \le \min(N, M, 200)) For example, if x, y, and z were 2, 3, and 2 respectively, there would now be Alicizers at (2, 3), (3, 3), (2, 4), and (3, 4). It is guaranteed that these newly placed Alicizers will not be "overlapping" any previously placed ones. It is also guaranteed that no Alicizers in the square will land outside of the empire.
2\ x\ y\ z Place down an Anti-Alicizer at position (x, y) of power level z (1 \le x \le N), (1 \le y \le M), (1 \le z \le \min(N, M, 200)). For example, if x, y, and z were 2, 3, and 2 respectively, the Alicizers at (2, 3), (3, 3), (2, 4), or (3, 4) would now be destroyed. It is guaranteed that there WILL be Alicizers fully encompassing the area being destroyed.
3\ x\ y\ z Query the length of the longest contiguous subsequence of Alicizers that goes strictly in one direction (Horizontal or Vertical), that includes at least one of the points in the range [x, x + z), [y, y + z). For example, if x, y, and z were 2, 3, and 2 respectively, the points in this range would be (2, 3), (3, 3), (2, 4), and (3, 4). (1 \le x \le N), (1 \le y \le M), (1 \le z \le \min(N, M, 200)).

It is guaranteed that for all queries, x + z \le N and y + z \le M.

Output Specification

For each type 3 query, print the result on a new line.

Constraints

Subtask 1 [30%]

1 \le N, M, Q \le 10^2, and z = 1 for all queries.

Subtask 2 [70%]

No additional constraints.

Sample Input

5 5 4
1 1 1 2
1 2 3 2
3 1 1 1
3 1 1 2

Sample Output

2
4

Note: Passing the sample is not required for passing the subtasks.

Explanation

After the first two queries of type 1, there are now Alicizers at (1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 3), (2, 4), (3, 4).

In the third query, only the position (1, 1) is in the range [x, x + z), [y, y + z).

The longest contiguous subsequence of Alicizers that spans strictly on one direction, that includes (1, 1), would either be the subsequence containing (1, 1) and (1, 2), or the subsequence containing (1, 1) and (2, 1). Both of these are of length 2.

In the last query, the positions (1, 1), (1, 2), (2, 1), (2, 2) are in the range [x, x + z), [y, y + z).

The longest contiguous subsequence of Alicizers that spans strictly on one direction, that includes any of these points, would be the subsequence containing (2, 1), (2, 2), (2, 3), and (2, 4), which is of length 4.


Comments

There are no comments at the moment.