Найбільший ланцюг#6784

Найбільший ланцюг

60 секунд

256 мегабайтів

Дуже легка

Визначимо частковий порядок $≺$ на трійках $a = (x_{a}, y_{a}, z_{a})$ \mathbf{a} = (x_a, y_a, z_a) та $b = (x_{b}, y_{b}, z_{b})$ \mathbf{b} = (x_b, y_b, z_b) таким чином:

$a ≺ b$ \mathbf{a} \prec \mathbf{b}, якщо $x_{a} < x_{b}$ x_a < x_b, $y_{a} < y_{b}$ y_a < y_b та $z_{a} < z_{b}$ z_a < z_b.

Дано набір трійок; знайдіть довжину найдовшої строго зростаючої послідовності трійок $a_{1} ≺ a_{2} ≺ \dots ≺ a_{k}$ \mathbf{a}_1 \prec \mathbf{a}_2 \prec \dotsb \prec \mathbf{a}_k.

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір описує набір трійок у такому форматі:

$m n A B$ m~n~A~B
$x_{1} y_{1} z_{1}$ x_1~y_1~z_1
$x_{2} y_{2} z_{2}$ x_2~y_2~z_2
$⋮$
$x_{m} y_{m} z_{m}$ x_m~y_m~z_m

Перший рядок містить чотири цілі числа: $m$ , $n$ , $A$ , $B$ . Всі значення $x_{i}$ x_i, $y_{i}$ y_i, $z_{i}$ z_i ( $1 \leq i \leq m$ 1 \le i \le m) — невід'ємні цілі числа.

Кожен набір містить $m + n$ m + n трійок. Перші $m$ трійок $p_{1}$ \mathbf{p}_1 до $p_{m}$ \mathbf{p}_m задані явно ( $p_{i} = (x_{i}, y_{i}, z_{i})$ \mathbf{p}_i = (x_i, y_i, z_i)). Решта $n$ трійок генеруються так, використовуючи параметри $A$ та $B$ :

int a = A, b = B, C = ~(1<<31), M = (1<<16)-1;
int r() {
    a = 36969 * (a & M) + (a >> 16);
    b = 18000 * (b & M) + (b >> 16);
    return (C & ((a << 16) + b)) % 1000000;
}

Викликайте $r ()$ всього $3 n$ разів, щоб послідовно згенерувати:

x_{m + 1}, y_{m + 1}, z_{m + 1}, x_{m + 2}, y_{m + 2}, z_{m + 2}, \dots, x_{m + n}, y_{m + n}, z_{m + n} .

x_{m+1},~y_{m+1},~z_{m+1},~x_{m+2},~y_{m+2},~z_{m+2},~\dotsc,~x_{m+n},~y_{m+n},~z_{m+n}.

Ви можете вважати:

1 \leq m + n \leq 3 \times 1 0^{5}, 1 \leq A, B \leq 2^{16}, 0 \leq x_{k}, y_{k}, z_{k} < 1 0^{6} для 1 \leq k \leq m + n .

1 \le m+n \le 3 \times 10^5,\\ 1 \le A,~B \le 2^{16},\\ 0 \le x_k,~y_k,~z_k < 10^6\quad \text{для}\ 1 \le k \le m+n.

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

Сума $m + n$ m+n по всіх наборах не перевищує $2 \times 1 0^{6}$ 2 \times 10^6.

Вихідні дані

Для кожного набору виведіть довжину $k$ найдовшої строго зростаючої послідовності трійок з цього набору — тобто найбільше $k$ таке, що $p_{i_{1}} ≺ p_{i_{2}} ≺ \dots ≺ p_{i_{k}}$ \mathbf{p}_{i_1} \prec \mathbf{p}_{i_2} \prec \dotsb \prec \mathbf{p}_{i_k}.

Приклади

Приклад 1