Snowy Streets

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.5s
Memory limit: 256M

Problem type

The North Pole is running out of funds! Santa Claus has started to work as an Oober driver in the prosperous city of Alert. For this job, Santa must drive people across Alert. The city can be seen as a grid with R rows and C columns. The square in the x^\text{th} row and y^\text{th} column is denoted as (x, y). Santa drives in a peculiar fashion: he will only drive directly down or right. To be more precise, if he is in (x, y), then he will only drive to either (x+1, y) or (x, y+1).

It's been snowing in Alert a lot recently, but Santa doesn't have enough money to buy proper winter tires. Due to this, he will not go through any squares with at least K millimeters of snow. Initially, all squares have 0 millimeters of snow.

There are two operations:

1 a b c d v The levels of snow of the squares in the subrectangle with opposing corners (a, b) and (c, d) increase by v millimeters each.
(1 \le a \le c \le R, 1 \le b \le d \le C, 1 \le v \le 10^9)

2 a b c d A query asking if it is possible for Santa to drive someone from (a, b) to (c, d). You may assume that Santa can get to the starting square. Note that if the starting or ending squares have levels of snow larger than or equal to K, then it is not possible.
(1 \le a \le c \le R, 1 \le b \le d \le C)

You are given Q of these operations. For each of the second operation, output yes if it is possible and no if it is not.


For all subtasks:
1 \le R \le 50
1 \le C \le 2000
1 \le K \le 10^9
1 \le Q \le 100\,000

Subtask 1 [30%]

(a, b)=(c, d) for all type 1 operations.
(a, b)=(1, 1) for all type 2 operations.

Subtask 2 [30%]

(a, b)=(1, 1) for all type 2 operations.

Subtask 3 [40%]

No additional restrictions.

Input Specification

The first line will contain four space-separated integers R, C, K, and Q.
The next Q lines will each contain an operation in the format specified above.

Output Specification

For each of the second operations, output its answer on a new line, in the order which they were asked.

Sample Input

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

Sample Output


Explanation for Sample

For the first operation, all levels of snow are 0, so Santa can clearly get from (1, 1) to (3, 5).
For the third operation, even though all the squares on any path from (1, 3) to (2, 5) have snow, the levels are still less than K, so Santa can pass through them.
For the sixth operation, there is only one way for Santa to get from (1, 1) to (3, 3). He has to move down twice, then right twice.
For the eighth operation, Santa cannot get from (1, 1) to (3, 3) since (3, 1), (2, 2), and (2, 3) have too much snow.
For the ninth operation, Santa can move right three times, then down twice.
For the tenth operation, the starting square has too much snow, so it is not possible.


There are no comments at the moment.