Solution for task #90 on @unilecs telegram channel

gistfile1.txt

<?php

function task90($n, $m, $b, $a, $points) {
    if ($n <= 0 || $m <= 0 || $b <= 0 || $a <= 0) throw new Exception('Incorrect input data');
    if ($b > $n || $a > $m) return 0;
    if ($b === 1 && $a === 1) return $n * $m - count($points);

    // сортируем массив занятых квадратов по X-координате в порядке возрастания X
    usort($points, function($p1, $p2) {
        return $p1[1] !== $p2[1] ? $p1[1] - $p2[1] : $p1[0] - $p2[0];
    });

    $curX = 1;
    $curY = 1;
    $cnt = 0;
    while ($curY <= $m - $a + 1) {
        while ($curX <= $n - $b + 1) {
            // находим X-координату ближайшего квадрата справа относительно текущего,
            // который занят какой-то грядкой и попадает по высоте в область
            // >= $curY и < $curY + $a (или же null, если таких квадратов нет)
            $closestX = findClosestX($curX, $curY, $points, $a);

            // определяем координату самого правого прямоугольника, который мы можем уложить в данный ряд
            // относительно текущей позиции
            $lastX = is_null($closestX) ? $n - $b + 1 : $closestX - $b;
            if ($lastX - $curX >= 0)  {
                $cnt += $lastX - $curX + 1;
            }
            $curX = $lastX + $b + 1;
        }
        $curX = 1;
        $curY++;
        // при переходе на следующий ряд удаляем из массива $points все квадраты,
        // расположенные выше нового текущего ряда, чтобы не учитывать их в последующих
        // вычислениях
        $points = array_filter($points, function($p) use ($curY) { return $p[0] >= $curY; });
    }
    return $cnt;
}


function findClosestX($x, $y, $points, $h) {
    foreach ($points as $p) {
        if ($p[1] >= $x && $p[0] >= $y && $p[0] < $y + $h) return $p[1];
    }
    return null;
}

function test($n, $m, $b, $a, $points) {
    printf("%d, %d, %d, %d, [%s] => %d\n",
        $n, $m, $b, $a,
        $points ? '(' . implode('),(', array_map(function($p) {
                                          return implode(',', $p);
                                       }, $points)) . ')' : '',
        task90($n, $m, $b, $a, $points)
    );
}

$points = [[1, 1], [1, 3], [2, 2], [2, 4], [3, 4], [4, 1]];

test(4, 4, 2, 2, $points);
test(5, 5, 2, 2, $points);
test(5000, 5000, 5001, 1, $points);
test(5000, 5000, 2, 2, []);
test(5000, 5000, 1, 1, $points);
test(5000, 5000, 2, 2, $points);
test(5000, 5000, 5000, 5000, []);
test(5000, 5000, 5000, 5000, $points);
test(5000, 5000, 2000, 2000, $points);

/* результаты тестов
4, 4, 2, 2, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 1
5, 5, 2, 2, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 4
5000, 5000, 5001, 1, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 0
5000, 5000, 2, 2, [] => 24990001
5000, 5000, 1, 1, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 24999994
5000, 5000, 2, 2, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 24989989
5000, 5000, 5000, 5000, [] => 1
5000, 5000, 5000, 5000, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 0
5000, 5000, 2000, 2000, [(1,1),(1,3),(2,2),(2,4),(3,4),(4,1)] => 9005988
*/