codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/35b2bc45087e60e1115fbd2111b69f6ff53f2173.png) 
     76 
     77 There are $4$ subrectangles of size $2$ consisting of only ones in it:
     78 
     79  ![](https://espresso.codeforces.com/cbda98d27be828f909212a98cb5025f01d5af623.png) 
     80 
     81 In second example matrix $c$ is:
     82 
     83  ![](https://espresso.codeforces.com/a04c6c01a1c02ac4c50895091ce0e09144c3cb81.png)