Adding Squares Codechef October Long challenge Problem Code

 Adding Squares  Codechef October Long challenge Problem Code-

problem Statement-

There are N$N$ different vertical lines on the plane, i$i$-th of which is defined by the equation x=ai$x=a_i$ (0≤ai≤W$0\le a_i\le W$) and M$M$ different horizontal lines, i$i$-th of which is defined by the equation y=bi$y=b_i$ (0≤bi≤H$0\le b_i\le H$). You must add one line of the form y=k$y=k$ (0≤k≤H$0\le k\le H$, k≠bi$k\ne b_i$ for every 1≤i≤M$1\le i\le M$) to the plane. What is the maximum possible number of squares with different areas you can obtain on the plane? (Squares can have other lines passing through them)

Input:

• First line will contain 4$4$ integers W$W$, H$H$, N$N$, M$M$
• Second line will contain N$N$ different integers a1,a2,...,aN$a_1,a_2,...,a_N$
• Third line will contain M$M$ different integers b1,b2,...,bM$b_1,b_2,...,b_M$

Output:

Output the maximal possible number of squares with different area on the plane after adding a new line.

Constraints

• 1≤W,H,N,M≤105$1\le W,H,N,M\le {10}^5$
• N≤W+1$N\le W+1$
• M≤H$M\le H$
• 0≤ai≤W$0\le a_i\le W$ for every 1≤i≤N$1\le i\le N$
• 0≤bi≤H$0\le b_i\le H$ for every 1≤i≤M$1\le i\le M$

Subtasks

• 50 points : 1≤H,W≤1000$1\le H,W\le 1000$
• 50 points : Original constraints

Sample Input:

10 10 3 3
3 6 8
1 6 10

Sample Output:

3

Explanation:

You can get 3$3$ different squares if you add a line y=4$y=4$. The three squares are:

• Square with top-left corner at (6, 6) and bottom-right corner at (8, 4) with an area of 4.
• Square with top-left corner at (3, 4) and bottom-right corner at (6, 1) with an area of 9.
• Square with top-left corner at (3, 6) and bottom-right corner at (8, 1) with an area of 25.

Link of Problem-https://www.codechef.com/problems/ADDSQURE

Solution -

Learn Bitset-

Follow the Link below for the bitset data structure and then follow my code.

C++ bitset and its application - GeeksforGeeks

www.geeksforgeeks.org › c-bitset-and-its-application

bitset - C++ Reference - Cplusplus.com

www.cplusplus.com › Reference › <bitset>

Code discussion It's a community where you people helps each other.

Join me on telegram-https://t.me/competitiveProgrammingDiscussion