AP and GP | Practice Problems

AP and GP

★★★★★

1 votes

Standard template library (STL), Easy

Details

Submissions

Discussion

Editorial

Problem

You are given $3$ sorted arrays $A$ , $B$ and $C$ of size $N$ . You have to count the number of triplets (one number in each array) such that they are in $GP$ for a given common ratio $R$ . Formally, number of indices $i$ , $j$ and $k$ such that $A[i]$ , $B[j]$ and $C[k]$ are in $GP$ and $(i ≤ j ≤ k)$ .

Similarly, you have to count the number of triplets (one number in each array) such that they are in $AP$ for a given common difference $D$ . Formally, number of indices $i$ , $j$ and $k$ such that $A[i]$ , $B[j]$ and $C[k]$ are in $AP$ and $(i ≤ j ≤ k)$ .

Input:

First line contains an integer $N$ , the size of the arrays.

Next line contains two integers $R$ and $D$ , common ratio and common difference respectively.

Next 3 lines contains the array $A$ , $B$ and $C$ respectively.

Output:

In a single line print the number of triplets in $GP$ and $AP$ separated by a single space.

Constraints:

$1$ ≤ $N$ ≤ $10$ ^$5$

$0$ ≤ $Array Elements$ , $R$ , $D$ ≤ $10$ ^$9$

Note: Consider $0, 0, 0$ are in GP.

Sample Input

6
2 2
1 2 2 3 4 7
2 3 4 5 6 8
2 3 4 5 7 8

Sample Output

3 3

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

The possible triplets in GP are:

$[1, 2, 4], [2, 4, 8], [2, 4, 8]$

The possible triplets in AP are:

$[1, 3, 5], [3, 5, 7], [4, 6, 8]$