An Animal Contest 1 P4 - Alpaca Arrays

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.75s
Java 2.0s
Python 2.0s
Memory limit: 256M

Problem types

Today, Tony the Alpaca needs some help with an array he found in the grass!

Tony gives you an array a of length N. He has Q questions to ask you about the array. Each question is of the form l_i, r_i, x_i, such that l_i \le r_i.

Given these parameters, Tony wants to know if there are 2 distinct indices p and q between l_i and r_i inclusive such that a_p \cdot a_q = x_i.

Also, since Tony hates numbers that are the same, a_p must not be equal to a_q. To keep Tony happy, you must answer all his questions!


1 \le N \le 10^6

1 \le Q \le 5\cdot10^4

1 \le a_i \le 10^5

1 \le l_i \le r_i \le N

1 \le x_i \le 10^5

Subtask 1 [10%]

1 \le N, Q, a_i \le 10^3

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line of input contains two integers N and Q.

The second line of input contains N integers a_i.

The final Q lines will each contain l_i, r_i, x_i, the parameters for the i^{th} query.

Output Specification

For each query, output YES if there are two distinct indices that multiply to x_i, and NO otherwise.

Sample Input 1

5 3
1 5 5 2 3
1 3 25
1 4 6
1 5 10

Sample Output 1


Sample Input 2

6 4
2 4 2 4 2 4
1 3 8
1 6 5
1 2 1
1 5 16

Sample Output 2



There are no comments at the moment.