1969: Запити на масиві

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 22,00 (partial)
Time limit: 1.0s
Java 2.0s
Python 3 2.0s
mono C# 2.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
zvit
Problem types

Дмитрик має масив ~a~ довжини ~N~.

У нього також є ~Q~ запитів по цьому масиву. ~i~-й запит має форму ~l_i, r_i, x_i~, при цьому ~l_i \le r_i~.

Допоможіть Дмитрику з'ясувати, чи існують 2 різні індекси ~p~ та ~q~ між ~l_i~ та ~r_i~ включно, такі що ~a_p \times a_q=x_i~.

Крім того, оскільки Дмитрик не переносить однакові числа, то ~a_p~ не повинно дорівнювати ~a_q~ .

Обмеження

  • ~1 \le N \le 10^6~
  • ~1 \le Q \le 5 \times 10^4~
  • ~1 \le a_i \le 10^5~
  • ~1 \le l_i \le r_i \le N~
  • ~1 \le x_i \le 10^5~

Input

Перший рядок вхідного потоку містить цілі числа ~N, Q~.

Наступний рядок містить ~N~ цілих чисел ~a_i~.

Наступні ~Q~ рядків містять цілі числа ~l_i, r_i, x_i~ - запити Дмитрика.

Всі числа у рядках розділяються пропуском.

Output

У вихідний потік вивести, в окремих рядках для кожного запиту, YES або NO

Sample Input 1

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

Sample Output 1

NO
NO
YES

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

YES
NO
NO
NO

Коментарі

Please read the guidelines before commenting.


  • 0
    Jodah  commented on Лис. 23, 2024, 8:46 після полудня

    Перевірте чи вистачає часу на пайтон


    • 1
      zvit  commented on Лис. 24, 2024, 9:22 до полудня

      так, вистачає. Існує розвʼязок на Пайтоні, який витрачає 1.1с на останній тест