Author: Yuto Watanabe

Overall consideration

If a cell is represented by ~(x, y)~, the values of ~x~ and ~y~ are called the ~x~-coordinate and the ~y~-coordinate, respectively. The values of ~a, b, c, d~, which determine the position of the garden, are called the left end, the right end, the upper end, and the lower end, respectively.

The artworks placed on the cells ~(x, y)~, ~(x+d, y)~ are the same, and the artworks placed on the cells ~(x, y)~, ~(x, y+d)~ are the same. So, there is no reason to make a garden whose horizontal width exceeds ~d~ or vertical height exceeds ~d~. Therefore, it is enough to consider the problem in the ~2~-dimensional torus in the range ~0 \le x < d~, ~0 \le y < d~ (namely, we consider ~x = 0~ and ~x = d-1~ are adjacent from left to right, and ~y = 0~ and ~y = d-1~ are adjacent from down to top). Then, the conditions for artworks of type A become ~a \le P_i \le b~ and ~c \le Q_i \le d~, and the conditions for artworks of type B become ~a \le R_j \le b~ or ~c \le S_j \le d~.

Subtask 1 (15 points)

Since it is bothering if the conditions contain the logical operator "or", we would like to remove them. For every artwork of type B, we check whether it satisfies one of ~a \le R_j \le b~ or ~c \le S_j \le d~. Then the conditions on the garden become a conjunction of conditions connected by the logical operator "and". Therefore, for each ~x,y~-coordinate, we need to solve the following problem (we call it Problem X):

• Assume that the integers between ~0~ and ~d-1~ are placed on a circle. We choose an interval on a circle so that some of the integers should be contained in the interval. Calculate the minimum length of the interval.

Problem X can be solved in time ~\mathcal{O}(D)~. Combining with the time to check every artwork, the total time complexity is ~\mathcal{O}(N + 2^M D)~.

Subtask 2 (6 points)

We check all the left ends, the right ends, the upper ends, and the lower ends. For every artwork among the ~N+M~ artworks, we need to check whether it satisfies the conditions. The total time complexity is ~\mathcal{O}(D^4(N+M))~.

Subtask 3 (8 points)

If we fix the left end, the right end, and the upper end, we need to consider the condition of the form "the lower end should be greater than ~*~" for every artwork among the ~N+M~ artworks. It is easy to calculate the optimal lower end. The total time complexity is ~\mathcal{O}(D^3(N+M))~.

Subtask 4 (16 points)

If we fix the left end and the right end, we need to solve Problem X for the ~y~-coordinates for every artwork among the ~N+M~ artworks. The total time complexity is ~\mathcal{O}(D^2(D+N+M))~.

Subtask 5 (30 points)

If we fix the left end, we decrease the right end one-by-one from ~b~. Then, in Problem X, the following queries are given successively:

• Remove an integer from the set of integers "which should be contained in the interval."
• Calculate the minimum length of the interval satisfying the conditions.

In other words, we need to solve a dynamical version of Problem X. This can be processed in ~\mathcal{O}(1)~ time per query using a data structure such as linked list.

If we shift the left end, we need only to consider artworks which have influence. For each fixed value of the right end, each object is considered at most once. Therefore, we can solve the task in ~\mathcal{O}(D(D+N+M))~ time.

Subtask 6 (25 points)

In Subtask 5, we consider all artworks which have influence when we shift the left end. If we can only consider artworks such that the number of integers "which should be contained in the interval" is decreased by one, the total time complexity is reduced to ~\mathcal{O}(D^2+N+M)~. This is possible if we appropriately keep track of

• the minimum value of ~R_j~ for artworks of type B satisfying ~S_j = y~ for each ~y~.

when we check all possible values of the right ends (concretely, we increase one-by-one from ~0~).