Count Squares
InterviewTime limit2sMemory limit512 MB
Given coordinates of h horizontal and v vertical lines, count how many axis-aligned squares have all four sides drawn by those lines.
- Level
Medium6 of 10
- Topics
- Array, Hash map, Two pointers, Combinatorics
- Solved
- No attempts yet
Problem
Alice took a clean sheet of paper and drew h horizontal and v vertical lines onto the paper.
The horizontal lines have y-coordinates y1, . . . , yh, and the vertical lines have x-coordinates x1, . . . , xv.
Given these coordinates, count the number of squares that appeared on the paper.
(The whole boundary of the square has to be drawn. The inside of the square does not have to be empty.)
Input
The first line of input contains the integers h and v (0 ≤ h, v ≤ 1500).
The second line of input contains a strictly increasing sequence consisting of h space-separated integers: y1, . . . , yh.
The third line of input contains a strictly increasing sequence consisting of v space-separated integers: x1, . . . , xv.
All horizontal and vertical coordinates are between 0 and 230, inclusive.
Output
Output a single line with a single integer: the total number of squares.
Hint
In the example there is one 1 × 1 square, one 2 × 2 square, and one 3 × 3 square.