1323B.md (2099B)
1 Source: https://codeforces.com/problemset/problem/1323/B 2 3 B. Count Subrectangles 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 How many subrectangles of size (area) $k$ consisting only of ones are there in $c$? 24 25 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$. 26 27 The size (area) of a subrectangle is the total number of cells in it. 28 29 Input 30 31 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. 32 33 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$), elements of $a$. 34 35 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \leq b_i \leq 1$), elements of $b$. 36 37 Output 38 39 Output single integer — the number of subrectangles of $c$ with size (area) $k$ consisting only of ones. 40 41 Examples 42 43 Input 44 45 ``` 46 3 3 2 47 1 0 1 48 1 1 1 49 ``` 50 51 Output 52 53 ``` 54 4 55 ``` 56 57 Input 58 59 ``` 60 3 5 4 61 1 1 1 62 1 1 1 1 1 63 ``` 64 65 Output 66 67 ``` 68 14 69 ``` 70 71 Note 72 73 In first example matrix $c$ is: 74 75  76 77 There are $4$ subrectangles of size $2$ consisting of only ones in it: 78 79  80 81 In second example matrix $c$ is: 82 83 