JDCC '17 Contest 3 S5 - Speed Interviewing

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

Similar to speed dating, during speed interviewing, you rapidly do a bunch of interviews!

The interviewers are situated in a grid formation (\(​R\) by ​C). Each interviewer has a rating score (from 1 to 100). However, due to certain events, interviewers will occasionally change in rating.

Hungry for interviews, Reyno will interview with everyone in a square area. Being both ambitious and lazy, he wants to achieve a certain total summed score with interviewers.

Input Specification

The first line contains three numbers, ​R C \(Q​\), the rows and column of the grid and the number of queries to answer.

The next ​R​ lines will each contain ​C​ numbers, representing the scores of the interviewers within the grid.

The next ​Q​ lines will contain a query of the following form:

  1. U r c s​ – the interviewer at location​ (r, c)​ now has a rating of ​s (1 \le s \le 100).

  2. S r c s​ – Reyno wants to know the side length of the square starting at ​(r, c)​ that has a total summed rating closest to s \((0 \le s​ \le 100​RC)\). If multiple squares are equally close, output the larger side length.

\(1 ​\le R, ​C ​\le 500\)

\(1 ​\le Q ​\le 10​^5\)

Output Specification

Output the answer to each S type query on its own line.

Sample Input

3 3 7
1 2 6
3 5 7
4 8 9
S 1 1 27
S 1 1 28
U 2 2 50
S 1 2 33
S 1 2 34
S 3 2 100
S 3 2 0

Sample Output


Explanation for Sample Output

The sum of the ratings for the answers of the S type queries are: 11, 45, 2, 65, 8, 8.


There are no comments at the moment.