Klasyczny problem zapytań#235
Dostajesz dwie liczby całkowite i oraz tablicę składającą się z liczb całkowitych. Masz zapytań w formacie l \: r \: x. Po każdym zapytaniu musisz:
odjąć od wszystkich elementów na przedziale [l;r] tablicy ;
powiedzieć, czy istnieje dobry przedział na tablicy . Przedział jest uważany za dobry, jeśli len(S) \ge L i avg(S) \le C, gdzie len(S) oznacza długość przedziału , a avg(S) oznacza średnią wartość na przedziale .
Pierwsza linia wejścia zawiera cztery liczby całkowite , (1 \le L \le n \le 2 \cdot 10^5), (1 \le q \le 2 \cdot 10^5), (-10^9 \le C \le 10^9).
Druga linia wejścia zawiera liczb całkowitych a_i (-10^9 \le a_i \le 10^9) — dana tablica .
Następne linii zawierają po trzy liczby całkowite , (1 \le l \le r \le n), (0 \le x \le 10^7) każda — opis zapytań.
Wypisz linii, z których każda składa się z YES, jeśli istnieje dobry przedział , lub NO w przeciwnym razie.
Przykład 1
( punktów): n \le 3;
( punktów): n \le 100, q \le 1000;
( punktów): q = 1, C = 0;
( punktów): C = 0;
( punktów): q = 1;
( punktów): brak dodatkowych ograniczeń.