Ansh and his love for Zeros
All submissions for this problem are available.Ansh likes the number $0$. So he gives his friend Dhruvik a puzzle to solve. He gives him a string $A_0$ of length $L$, which has all zeros (if $N=4$, A = "$0000$"). He then gives him a list of $R$ changes, which changes the string.The $j-th$ change in the list changes the string $A$$j-1$ to $A_j$, so at the end of the list (that is, after $R$ changes) the string we get is $A_R$. Every change consists of two positive integers $X_j$ and $Y_j$. All the ones in the range $[X_j,Y_j]$ (both inclusive) are changed into zeros, and all zeros in that range are set to one. Ansh challenges Dhruvik to find out which among the $R+1$ strings ($A_0,A_1,...,A_R$) is the greatest lexicographical string. Can you help Dhruvik to find the right string? ###Input: - The first line of the input contains two integers, $L$ and $R$. - The $j-th$ of the next R lines contains two integers, $X_j$ and $Y_j$, ###Output: - Print a single line containing the answer string. ###Constraints - $1 \leq L,R \leq 100,000$ - $1 \leq X_j \leq Y_j \leq L$ ###Subtasks - 40 points : $L \leq 2000$ - 60 points : Original Constraints ###Sample Input 1: 8 4 1 7 7 8 4 7 3 6 ###Sample Output 1: 11111110
|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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.