SubInversing

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You initially start with a binary string S_{0} which is of length N and has all 0s. You are then given U updates, which keep transforming the string. The ith update transforms the string S_{i1} into S_{i}, and hence after all the U updates you will be left with S_{U}.
A single update is of the form (L_{i}, R_{i}), which means that all the 1s in the range [L_{i}, R_{i}] (both end points included) should be changed into 0s, and all the 0s in that range should be changed to 1s.
You need to find out which among the U+1 binary strings: S_{0}, S_{1}, .., S_{U}, is lexicographically the largest, and print that string.
Input
 The first line of the input contains two integers, N, and U, denoting the length of the string and number of updates respectively.
 The ith of the next U lines contains two integers, L_{i} and R_{i}, which denotes that the ith update is to swap all the values in the string which fall between the indices L_{i} and R_{i} (both inclusive).
 1 ≤ N, U ≤ 100,000
 1 ≤ L_{i} ≤ R_{i} ≤ N
 Subtask #1 (20 points): 1 ≤ N ≤ 2000
 Subtask #2 (80 points): Original constraints.
Output
Output a single line containing one binary string  the lexicographically largest string among the U+1 strings.
Constraints
Subtasks
Example
Input: 10 10 9 10 6 10 9 10 1 8 3 5 3 3 3 4 3 9 4 8 7 7 Output: 1111100011
Explanation
Let us see what happens in each operation:
The lexicographically largest among these is 1111100011 and so, that is the answer.
Author:  gainullinildar 
Tester:  melfice 
Editorial  https://discuss.codechef.com/problems/SUBINVER 
Tags  gainullinildar, hashes, ltime48, mediumhard, persistence, segmenttree 
Date Added:  26052017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 