The first subtask is troll.

To solve the second subtask, it is enough to check the conditions directly. To determine if there is cake at ~(i,j)~, two conditions must be met:

• Row ~i~ contains cake at positions between ~c_i~ and ~d_i~. This cell will contain cake if ~c_i \le j \le d_i~. Otherwise, this cell will not contain cake.
• Column ~j~ contains cake at positions between ~r_j~ and ~s_j~. This cell will contain cake if ~r_j \le i \le s_j~. Otherwise, this cell will not contain cake.

If exactly one of these conditions is met, then the cell ~(i,j)~ is unclear. Otherwise, it is clear.

Next, we want to check if the cake is connected. It is enough to generate the cake, perform a BFS/DFS graph search, and then check if all cells of the cake are visited.

Time Complexity: ~\mathcal{O}(RC)~

There are various ways to solve subtask 3. The intended solution was to use 3 segment trees. Consider all of the rows of the cake.

• The first segment tree will store the first row to have cake in a specific column. For the ~j^{th}~ column, call this value ~first(j)~.
• The second segment tree will store the last row to have cake in a specific column. For the ~j^{th}~ column, call this value ~last(j)~.
• The third segment tree will store the number of rows that have cake in a specific column. For the ~j^{th}~ column, call this value ~count(j)~.

Now, for each column ~j~, we check if the segment trees agree with ~r_j~ and ~s_j~. First of all, the amount of cake must agree. That is, ~count(j) = s_j-r_j+1~. Also, the starting and ending positions must agree too. That is, ~first(j)=r_j~ and ~last(j)=s_j~.

If any of these conditions is false, there must be an unclear cell in this column. To find an unclear cell, check each of the ~\mathcal{O}(R)~ cells in this column to find it. We already have a way to determine if there is cake at ~(i,j)~.

If there are no unclear cells, it is time to check if the cake is connected. Notice that if a row can be visited, all of the cake in that row can be visited. If it is always possible to move between two adjacent rows, then the cake is connected (otherwise, it is unconnected).

There are only 2 cases where adjacent rows are unconnected.

Time Complexity: ~\mathcal{O}(R+C \log R)~

Note: It might be possible to solve this problem with a time complexity of ~\mathcal{O}(R+C)~.