Count Subrectangles (Codeforces 1323B)
Tags: Greedy, binary search

You are given an array $$$a$$$ of length $$$n$$$ and array $$$b$$$ of length $$$m$$$ both consisting of only integers $$$0$$$ and $$$1$$$. Consider a matrix $$$c$$$ of size $$$n \times m$$$ formed by following rule: $$$c_{i, j} = a_i \cdot b_j$$$ (i.e. $$$a_i$$$ multiplied by $$$b_j$$$). It's easy to see that $$$c$$$ consists of only zeroes and ones too.How many subrectangles of size (area) $$$k$$$ consisting only of ones are there in $$$c$$$?A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers $$$x_1, x_2, y_1, y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$) a subrectangle $$$c[x_1 \dots x_2][y_1 \dots y_2]$$$ is an intersection of the rows $$$x_1, x_1+1, x_1+2, \dots, x_2$$$ and the columns $$$y_1, y_1+1, y_1+2, \dots, y_2$$$.The size (area) of a subrectangle is the total number of cells in it.

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$$$), length of array $$$a$$$, length of array $$$b$$$ and required size of subrectangles.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), elements of $$$a$$$.The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 1$$$), elements of $$$b$$$.

Output: Output single integer — the number of subrectangles of $$$c$$$ with size (area) $$$k$$$ consisting only of ones.

Note: In first example matrix $$$c$$$ is:  There are $$$4$$$ subrectangles of size $$$2$$$ consisting of only ones in it:  In second example matrix $$$c$$$ is:  

Sample Inputs:
3 3 2
1 0 1
1 1 1

3 5 4
1 1 1
1 1 1 1 1

Sample Outputs:
4

14

Solution (Python):
(n, m, k) = map(int, input().split())
a = [len(i) for i in input().replace(' ', '').split('0') if len(i) > 0]
b = [len(i) for i in input().replace(' ', '').split('0') if len(i) > 0]
d = [(i, k // i) for i in range(1, int(k ** 0.5) + 1) if k % i == 0]
d += [(j, i) for (i, j) in d if i != j]
c = 0
for (x, y) in d:
    c += sum((i - x + 1 for i in a if x <= i)) * sum((j - y + 1 for j in b if y <= j))
print(c)

Solution (Python):
import math
import sys
import time

class SolutionFramework:

    def __init__(self):
        self._input_lines = []
        self._cur_index = 0
        self._expected_lines = []
        self._output_lines = []

    def solve(self, input_file, output_file):
        raise NotImplementedError()

    def test(self):
        start = time.time()
        self.solve(self, self)
        if self._expected_lines != self._output_lines:
            print(f'Failed, {self._expected_lines} != {self._output_lines}')
        else:
            print('Succeeded')
        print('Consumed:', time.time() - start)

    def readline(self):
        cur_line = self._input_lines[self._cur_index]
        self._cur_index += 1
        return cur_line

    def read(self, limit=0):
        return self.readline()

    def write(self, data):
        if data == '\n':
            return
        self._output_lines.append(data)

    def flush(self):
        pass

class A(SolutionFramework):

    def __init__(self):
        super().__init__()
        self._input_lines = ['3', '3', '1 4 3', '1', '15', '2', '3 5']
        self._expected_lines = ['1', '2', '-1', '2', '1 2']

    def solve(self, input_file, output_file):
        test_num = int(input_file.readline())
        for _ in range(test_num):
            seq_len = int(input_file.readline())
            seq = [int(x) for x in input_file.readline().split()]
            odd_index = -1
            odd_val = -1
            for (index, x) in enumerate(seq):
                if x % 2 == 0:
                    print(1, file=output_file)
                    print(index + 1, file=output_file)
                    break
                elif odd_val == -1:
                    odd_val = x
                    odd_index = index
                else:
                    print(2, file=output_file)
                    print(f'{odd_index + 1} {index + 1}', file=output_file)
                    break
            else:
                print(-1, file=output_file)

class B(SolutionFramework):

    def __init__(self):
        super().__init__()
        self._input_lines = '3\n5\n1 3\n1 2\n3 3\n5 5\n4 3\n2\n1 0\n0 1\n1\n4 3'.splitlines(keepends=False)
        self._expected_lines = 'YES\nRUUURRRRUU\nNO\nYES\nRRRRUUU'.splitlines(keepends=False)

    def solve(self, input_file, output_file):
        test_num = int(input_file.readline())
        for _ in range(test_num):
            pack_num = int(input_file.readline())
            pack_points = []
            for _ in range(pack_num):
                (x_str, y_str) = input_file.readline().split()
                (x, y) = (int(x_str), int(y_str))
                pack_points.append((x, y))
            sorted_points = sorted(pack_points, key=lambda p: p[0] + p[1])
            (x, y) = (0, 0)
            steps = []
            for point in sorted_points:
                (next_x, next_y) = point
                if next_x < x or next_y < y:
                    print('NO', file=output_file)
                    break
                if next_x > x:
                    steps.append('R' * (next_x - x))
                if next_y > y:
                    steps.append('U' * (next_y - y))
                (x, y) = (next_x, next_y)
            else:
                print('YES', file=output_file)
                print(''.join(steps), file=output_file)

class C(SolutionFramework):

    def __init__(self):
        super().__init__()
        import random
        random.seed(0)
        self._sample = []
        for i in range(int(500000.0)):
            self._sample.append('(')
            self._sample.append(')')
        random.shuffle(self._sample)
        self._input_lines = [str(int(1000000.0)), ''.join(self._sample)]
        self._input_lines = [14, '(())(()))())((']
        self._expected_lines = ['0']

    def solve(self, input_file, output_file):
        length = int(input_file.readline())
        if length == 0:
            print(0, file=output_file)
            return
        sample = input_file.read(length)
        if length % 2 != 0:
            print(-1, file=output_file)
            return
        cost = 0
        area_stack = [(0, len(sample) - 1)]
        while area_stack:
            (start, end) = area_stack[-1]
            area_stack.pop()
            area_start_index = start
            balance = 0
            cur_index = start
            while cur_index <= end:
                inc_balance = 1 if sample[cur_index] == '(' else -1
                balance += inc_balance
                if balance == 0:
                    (area_start, area_end) = (area_start_index, cur_index)
                    if sample[area_start] != '(':
                        cost += area_end - area_start + 1
                    area_start_index = cur_index + 1
                cur_index += 1
            if balance != 0:
                print(-1, file=output_file)
                return
        print(cost, file=output_file)

    def _take_off_wrapping_brackets(self, sample, start, end):
        left_count = 0
        left_index = start
        while sample[left_index] == '(':
            left_index += 1
            left_count += 1
        right_count = 0
        right_index = end
        while sample[right_index] == ')':
            right_index -= 1
            right_count += 1
        pair_count = min(left_count, right_count)
        if pair_count > 0:
            pair_count -= 1
        return (start + pair_count, end - pair_count)

class D(SolutionFramework):

    def __init__(self):
        super().__init__()
        self._input_lines = ['4 4 2', '1 0 1 1', '1 1 0 1']
        self._expected_lines = ['6']
        self._input_lines = ['1 1 1', '0', '0']
        self._expected_lines = ['0']

    def solve(self, input_file, output_file):
        (n, m, k) = (int(x) for x in input_file.readline().split())
        a_list = [int(x) for x in input_file.readline().split()]
        b_list = [int(x) for x in input_file.readline().split()]
        assert len(a_list) == n
        assert len(b_list) == m
        a_ones = self._get_consecutive_one_map(a_list)
        b_ones = self._get_consecutive_one_map(b_list)
        k_xy = []
        for i in range(1, math.floor(math.sqrt(k)) + 1):
            if k % i == 0:
                k_xy.append((i, k // i))
        matrix_total = 0
        for (a_len, a_len_num) in a_ones.items():
            for (b_len, b_len_num) in b_ones.items():
                if a_len * b_len < k:
                    continue
                (a, b) = (a_len, b_len)
                times = a_len_num * b_len_num
                for (x, y) in k_xy:
                    if a >= x and b >= y:
                        matrix_total += (a - x + 1) * (b - y + 1) * times
                    if x == y:
                        continue
                    if b >= x and a >= y:
                        matrix_total += (b - x + 1) * (a - y + 1) * times
        print(matrix_total, file=output_file)

    def _get_consecutive_one_map(self, zero_one_list):
        length = 0
        one_map = {}
        for num in zero_one_list:
            if num == 0:
                if length > 0:
                    one_map[length] = one_map.get(length, 0) + 1
                    length = 0
            else:
                length += 1
        if length > 0:
            one_map[length] = one_map.get(length, 0) + 1
        return one_map
if __name__ == '__main__':
    D().solve(sys.stdin, sys.stdout)

Solution (Python):
(n, m, k) = map(int, input().split())
a = [len(i) for i in input().replace(' ', '').split('0') if len(i) > 0]
b = [len(i) for i in input().replace(' ', '').split('0') if len(i) > 0]
d = [(i, k // i) for i in range(1, int(k ** 0.5) + 1) if k % i == 0]
d += [(j, i) for (i, j) in d if i != j]
c = 0
for (x, y) in d:
    c += sum((i - x + 1 for i in a if x <= i)) * sum((j - y + 1 for j in b if y <= j))
print(c)