Ən böyük zəncir#6784

Ən böyük zəncir

60 saniyə

256 meqabayt

Çox asan

Üçlülər $a = (x_{a}, y_{a}, z_{a})$ \mathbf{a} = (x_a, y_a, z_a) və $b = (x_{b}, y_{b}, z_{b})$ \mathbf{b} = (x_b, y_b, z_b) üzərində qismən sıralama $≺$ belə müəyyənləşdirilir:

Əgər $x_{a} < x_{b}$ x_a < x_b, $y_{a} < y_{b}$ y_a < y_b və $z_{a} < z_{b}$ z_a < z_b isə $a ≺ b$ \mathbf{a} \prec \mathbf{b}.

Verilən üçlü dəstində ən uzun ciddi artan ardıcıllığın uzunluğunu tapın: $a_{1} ≺ a_{2} ≺ \dots ≺ a_{k}$ \mathbf{a}_1 \prec \mathbf{a}_2 \prec \dotsb \prec \mathbf{a}_k.

Giriş

Giriş bir neçə datasetdən ibarətdir. Hər dataset üçlü dəstini aşağıdakı formatda təsvir edir:

- $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

Birinci sətrdə dörd tam ədəd var: $m$ , $n$ , $A$ , $B$ . Bütün $x_{i}$ x_i, $y_{i}$ y_i, $z_{i}$ z_i ( $1 \leq i \leq m$ 1 \le i \le m) qeyri-mənfi tam ədədlərdir.

Hər datasetdə ümumilikdə $m + n$ m + n üçlü olur. İlk $m$ üçlü $p_{1}$ \mathbf{p}_1-dən $p_{m}$ \mathbf{p}_m-ə qədər açıq şəkildə verilir ( $p_{i} = (x_{i}, y_{i}, z_{i})$ \mathbf{p}_i = (x_i, y_i, z_i)). Qalan $n$ üçlü isə $A$ və $B$ parametrlərindən istifadə etməklə aşağıdakı kimi yaradılır:

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 ()$ funksiyasını $3 n$ dəfə çağırın ki, aşağıdakı ardıcıllıqla ədədlər alınsı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}.

Aşağıdakıları qəbul edin:

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} u ¨ c ¸ u ¨ n 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{üçün}\ 1 \le k \le m+n.

Giriş dörd sıfırdan ibarət sətrlə bitir.

Bütün datasetlər üzrə $m + n$ m+n cəmi $2 \times 1 0^{6}$ 2 \times 10^6-dan çox olmur.

Çıxış

Hər dataset üçün verilmiş dəstdə ən uzun ciddi artan ardıcıllığın uzunluğunu çıxarın — yəni, $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} maksimal $k$ üçün cavabı verin.

Nümunələr

Nümunə 1