Skip to content

Instantly share code, notes, and snippets.

@miau
Last active August 29, 2015 14:01
Show Gist options
  • Save miau/f69653684c084f1f3ccd to your computer and use it in GitHub Desktop.
Save miau/f69653684c084f1f3ccd to your computer and use it in GitHub Desktop.
A solution for paiza online hackathon Vol.2 https://paiza.jp/poh/paizen
<?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
);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment