I tried this problem on Hackerearth :

Link

The editorial is not provided, just the code is there. I cannot understand how the author did it.

Please try this problem and please explain the approach. Can this also be done using combinatorics?

Edit 1: I spent my whole day waiting for the solution from CF community. I don't know why anyone doesn't want to help a struggling coder. :(

Edit 2: I would request people that if they cannot help then atleast don't downvote someone's blog.

Edit 3: I was wrong about the CF community. You all are kind and helpful people. :D

I couldn't solve this. Please do tell me any simple approach which can pass the time constraint.

Problem:

You are given n intervals which are termed as special intervals. Each interval is of a different type.

Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval.

Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval.

Input format

First line: n denoting the number of special intervals

Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.

Next line: q denoting the number of non-special intervals

Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval.

Output format

print q space-seperated integers denoting the answer for each of the q non-special integers.

Constraints

1<=n<=10^5

-10^9<=lspecial[i]<=10^9

-10^9<=rspecial[i]<=10^9

1<=q<= 5 * 10^4

-10^9<=lnonspecial[i]<=10^9

-10^9<=rnonspecial[i]<=10^9

Sample Input

3

1 2

1 5

1 7

3

1 3

3 3

6 7

Sample Output

3 2 1

Time Limit 1 second

I thought of a solution but I have a doubt if my solution will work.

Please tell your solution of solving it, also a little analysis of the time complexity(if you have time)

Here's the Problem:

Given two arrays of integers A and B of size N each, where each pair (A[i], B[i]) for represents a unique point (x, y) in the 2D Cartesian plane.

Find and return the number of unordered quadruplet (i, j, k, l) such that (A[i], B[i]), (A[j], B[j]), (A[k], B[k]) and (A[l], B[l]) form a rectangle with the rectangle having all the sides parallel to either x-axis or y-axis.

Input Format The first argument given is the integer array A. The second argument given is the integer array 8.

Output Format Return the number of unordered quadruplets that form a rectangle.

Constraints

1<=N<=2000

1<=A[i],B[i]<=10^9

For Example:

Input 1: A=[1,1,2,2] B=[1,2,1,2]

Output 1: 1

Input 2: A=[1,1,2,2,3,3] B=[1,2,1,2,1,2]

Output 2: 3