| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 12 | 6 | 4 | 66.667% |
На всемирной олимпиаде роботов проводятся соревнования по робогольфу. Поле, на котором происходит игра, имеет вид прямоугольника, состоящего из $n \times m$ единичных квадратов. Строки поля пронумерованы числами от 1ドル$ до $n,ドル а столбцы --- от 1ドル$ до $m$. Таким образом, каждый квадрат характеризуется двумя положительными целыми числами $r$ и $c$ --- номерами строки и столбца, на пересечении которых он находится.
Два робота по очереди перемещают специальную фишку по полю, в некоторых квадратах которого находятся ловушки. Если фишка находится в квадрате $(r, c),ドル то робот, выполняющий очередной ход, может переместить её в квадрат $(r + 1, c)$ или в квадрат $(r, c + 1)$. Если соответствующего квадрата не оказалось, поскольку фишка находится в последней строке или в последнем столбце поля, робот может переместить её за границу поля. Игра заканчивается в том случае, когда фишка оказывается либо за границей поля, либо в квадрате с ловушкой.
Каждой ловушке соответствует некоторое целое число $v_i$ --- её цена. Результат игры равен значению цены ловушки, в которой закончилась игра, или равен 0, если фишка оказалась за границей поля. Робот, который делает ход первым, стремится минимизировать результат игры, а робот, который делает ход вторым --- максимизировать.
Пусть фишка вначале находится в квадрате $(r, c)$. Гарантированный результат игры $g(r, c)$ для этого квадрата равен минимальному возможному результату игры, которого может добиться делающий первый ход робот вне зависимости от действий соперника. Поскольку стартовый квадрат до начала матча неизвестен, разработчики роботов хотят вычислить сумму значений $g(r, c)$ для всех квадратов поля.
Требуется написать программу, которая по заданным расположениям и ценам ловушек определит сумму гарантированных результатов игры по всем квадратам поля.
Первая строка входных данных содержит три целых числа $n,ドル $m$ и $k$ (1ドル \le n, m \le 10 ^ 9$; 1ドル \le k \le \min(n \cdot m, 10 ^ 5)$) --- количество строк, количество столбцов и количество ловушек, соответственно.
Следующие $k$ строк содержат по три целых числа $r_i,ドル $c_i$ и $v_i$ (1ドル \le r_i \le n,ドル 1ドル \le c_i \le m,ドル $-10^9 \le v_i \le 10 ^ 9$) --- номер строки, номер столбца и цену $i$-й ловушки соответственно. Никакие две ловушки не находятся в одном и том же квадрате.
Выведите одно целое число --- остаток от деления суммы гарантированных результатов игры по всем квадратам поля на число 998ドル,244円,353円$.
Остаток от деления $a$ на $b,ドル где $a$ может быть отрицательным, равен числу $r = a \bmod b,ドル лежащему в диапазоне от 0ドル$ до $b-1,ドル такому что $a = qb + r,ドル где $q$ --- целое. Например, 13ドル \bmod 4 = 1,ドル $-13 \bmod 4 = 3,ドル 12ドル \bmod 4 = 0,ドル $-12 \bmod 4 = 0$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $n, m \le 1,000円$ |
| 2 | 14 | $n \le 5,ドル $m \le 10 ^ 9$ |
| 3 | 14 | $n, m \le 100,000円,ドル $k = n + m - 1,ドル для любого $i,ドル $r_i = n$ или $c_i = m$ |
| 4 | 10 | для любого $i,ドル $r_i \ge n - 1,000円$ и $c_i \ge m - 1,000円$ |
| 5 | 6 | $n, m \le 100,000円,ドル для любого $i,ドル $v_i = 1$ |
| 6 | 6 | $i,ドル $v_i = 1$ |
| 7 | 10 | $n, m \le 100,000円$ |
| 8 | 10 | $k \le 1,000円$ |
| 9 | 10 |
3 3 3 2 3 -2 3 1 3 1 2 1
998244352
2 4 3 1 2 2 2 4 -3 2 1 1
998244348
В первом примере гарантированные результаты игр для всех квадратов выглядят так (квадраты с ловушками выделены):
Сумма результатов равна: 1ドル + 1 -ひく 2 +たす 0 -ひく 2 -ひく 2 +たす 3 +たす 0 +たす 0 =わ -ひく1$. Ответ равен $(-1) \bmod 998,244円,353円 = -1 + 998,244円,353円 = 998,144円,352円$.
В втором примере гарантированные результаты игр для всех квадратов выглядят так (квадраты с ловушками выделены):
Сумма результатов равна: 1ドル + 2 +たす 0 -ひく 3 +たす 1 +たす 0 -ひく 3 -ひく 3 =わ -ひく5$. Ответ равен $(-5) \bmod 998,244円,353円 = 998,244円,348円$.