A solution for paiza online hackathon Vol.2 https://paiza.jp/poh/paizen

poh2.php

<?php
fscanf(STDIN, '%d%d', $h, $w);
$rawMap = stream_get_contents(STDIN, $h * ($w + 1));

$chars = "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f !\"#\$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\x7f\x80\x81\x82";
$rawMap = strtr($rawMap, '1', "\0");
$rawMap = strtr($rawMap, "\n", "\xff");
$rawMap = preg_replace_callback(
    '/0+/',
    function($m) use ($chars, $w) {
        return substr($chars, 0, strlen($m[0]));
    },
    $rawMap
);
$rawMap .= str_repeat("\0", $w);
$map = explode("\xff", $rawMap);

$start = array();
$last = 0;
for ($x = 0; $x < $w; $x++) {
    for ($y = 0; $y < $h + 1; $y++) {
        $width = ord($map[$y][$x]);
        for ($i = $width + 1; $i <= $last; $i++) {
            $height = $y - $start[$i];
            if (isset($preCount[$i][$height])) {
                $preCount[$i][$height]++;
            } else {
                $preCount[$i][$height] = 1;
            }
        }
        for ($i = $last + 1; $i <= $width; $i++) {
            $start[$i] = $y;
        }
        $last = $width;
    }
}

$count = array();
foreach ($preCount as $width => $heightCounts) {
    foreach ($heightCounts as $height => $cnt) {
        for ($y = 1; $y <= $height; $y++) {
            if (isset($count[$width][$y])) {
                $count[$width][$y] += ($height - $y + 1) * $cnt;
            } else {
                $count[$width][$y] = ($height - $y + 1) * $cnt;
            }
        }
    }
}

fgets(STDIN);
$data = stream_get_contents(STDIN);
echo preg_replace_callback(
    '/([0-9]+) ([0-9]+)/S',
    function($m) use ($count) {
        return isset($count[$m[2]][$m[1]]) ? $count[$m[2]][$m[1]] : 0;
    },
    $data
);