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 S0 which is of length N and has all 0s. You are then given U updates, which keep transforming the string. The i-th update transforms the string Si-1 into Si, and hence after all the U updates you will be left with SU.
A single update is of the form (Li, Ri), which means that all the 1s in the range [Li, Ri] (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: S0, S1, .., SU, is lexicographically the largest, and print that string.
- The first line of the input contains two integers, N, and U, denoting the length of the string and number of updates respectively.
- The i-th of the next U lines contains two integers, Li and Ri, which denotes that the i-th update is to swap all the values in the string which fall between the indices Li and Ri (both inclusive).
- 1 ≤ N, U ≤ 100,000
- 1 ≤ Li ≤ Ri ≤ N
- Subtask #1 (20 points): 1 ≤ N ≤ 2000
- Subtask #2 (80 points): Original constraints.
Output a single line containing one binary string - the lexicographically largest string among the U+1 strings.
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
Let us see what happens in each operation:
The lexicographically largest among these is 1111100011 and so, that is the answer.
|Tags||gainullinildar, hashes, ltime48, medium-hard, persistence, segment-tree|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.