시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 2 | 2 | 100.000% |
Для геологической разведки перед добычей радия на плато Меридиана на орбиту Марса выведен специальный спутник, позволяющий измерять уровень радиоактивности на поверхности.
Представим плато как прямоугольник, состоящий из $n \times m$ единичных квадратов, обозначим $j$-й квадрат в $i$-м ряду как $(i, j)$.
В результате сканирования плато для каждого единичного квадрата был определён уровень радиоактивности. Уровень радиоактивности квадрата $(i, j)$ задаётся целым положительным числом $a_{ij}$. Точность измерений настолько велика, что все числа $a_{ij}$ различны. Единичный квадрат $(i, j)$ считается подходящим для добычи радия, если значение $a_{ij}$ является максимальным в $i$-й строке, а также максимальным в $j$-м столбце.
В процессе наблюдений было проведено $q$ последовательных уточнений уровня радиоактивности. А именно, $k$-е уточнение изменяло значение $a_{r_kc_k}$ на некоторое строго большее значение. При этом после каждого уточнения все значения $a_{ij}$ оставались различными.
Требуется написать программу, которая по заданным исходным значениям $a_{ij}$ и списку уточнений после каждого уточнения информации определяет количество подходящих для добычи радия единичных квадратов.
Первая строка входных данных содержит три положительных целых числа: $n$, $m$ и $q$ ($1 \le n\times m \le 200\,000$, $1 \le q \le 200\,000$). Обратите внимание, что ограничение сверху дано на площадь плато, а не на количество столбцов и строк по отдельности.
Следующие $n$ строк содержат по $m$ положительных целых чисел, $j$-е число в $i$-й из этих строк задаёт начальное значение $a_{ij}$ ($1 \le a_{ij} \le 10^7$, все $a_{ij}$ различны).
Следующие $q$ строк описывают уточнения данных, $k$-я из них содержит три целых числа $r_k$, $c_k$ и $x_k$ и задаёт изменение информации об уровне радиоактивности единичного квадрата $(r_k, c_k)$, новое значение равно $x_k$ ($1 \le r_k \le n$, $1 \le c_k \le m$, $1 \le x_k \le 10^7$). Гарантируется, что $x_k$ строго больше предыдущего уровня радиоактивности в этом квадрате, и что все уровни радиоактивности различны после каждого изменения.
Выходные данные должны содержать $q$ строк, в $k$-й из этих строк требуется вывести одно число --- количество подходящих для добычи радия единичных квадратов после $k$-го обновления информации.
번호 | 배점 | 제한 |
---|---|---|
1 | 25 | $1 \le n\times m \le 100$, $1 \le q \le 100$ |
2 | 25 | $1 \le n\times m \le 5000$, $1 \le q \le 5000$ |
3 | 25 | $1 \le n \le 400$, $1 \le m \le 400$, $1 \le q \le 200\,000$ |
4 | 25 | $1 \le n\times m \le 200\,000$, $1 \le q \le 200\,000$ |
2 3 3 1 4 3 6 5 2 2 2 9 1 3 5 2 2 10
1 2 2