Paint the Wall
All submissions for this problem are available.Professor Sahil is a master artist, he always finds creative ways to teach lessons to his students. Today in Painting class he took all the students of the class to a wall. Professor Sahil asked every student to paint the wall upto a certain integral height one by one (second boy starts once the first boy finishes painting) from the bottom with any color of their wish, except a student Mudit who was made to stand behind the wall and note down all the data i.e the height upto which each student painted and the color $Ci$ every student used. At the end of the painting session Professor asked Mudit to tell how many distinct colors are there on the wall. Mudit being a weak student asked you for help. Formally, given a wall of infinite height, initially unpainted. There occur $N$ operations, and in ith operation, the wall is painted upto height $Hi$ with color $Ci$. Suppose in jth operation (j>i) wall is painted upto height $Hj$ with color $Cj$ such that $Hj$ >= $Hi$, the $Cith$ color on the wall is hidden. At the end of $N$ operations, you have to find the number of distinct colors(>=1) visible on the wall. Help him find out the number of distinct colors on the wall. ###Input: - The first line consists of single integer $T$ denoting the number of test cases. - The second line contains 2 space separated integers $N$ and $M$, denoting the number of students and number of colors available (1 to $M$). - The third line contains $N$-space separated integers ($Hi$ ) denoting the height upto which each student painted the wall. - The fourth line contains $N$ space separated integers denoting the color ( $Ci$ ) the ith student used. ###Output: Print the number for distinct colors on the wall for each test case. ###Constraints - $1 \leq T \leq 100$ - $1 \leq N ,M \leq 10^5$ - **Sum of N over all test cases <= $5*10^5$** - **Sum of M over all test cases <=$5*10^5$** - $1 \leq Hi \leq10^9$ - $1 \leq Ci \leq M$ ###Sample Input: 3 5 4 1 2 3 4 5 3 3 3 3 3 5 4 3 5 1 2 3 1 2 3 4 3 5 5 5 4 3 2 3 1 2 3 4 5 ###Sample Output: 1 2 3 ###EXPLANATION: In the first test case, painted upto height 1, 2, 3, 4, 5 in the five operations, all with the same color. Hence, the number of distinct colors is 1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.