530D.md (1307B)
1 Source: https://codeforces.com/problemset/problem/530/D 2 3 D. Set subtraction 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a starting set consisting of all integers from 1 to 1000, inclusive. You are also given several sets which need to be subtracted from the starting set (i.e., each number which is in at least one of these sets needs to be removed from the starting set). Each subtracted set is represented as an interval of integers from *A* to *B*, inclusive. Output the result after all subtractions. 22 23 Input 24 25 The first line of input contains an integer *N* (0 ≤ *N* ≤ 100) — the number of intervals to be subtracted. The following *N* lines contain pairs of integers *A* and *B* (1 ≤ *A* ≤ *B* ≤ 1000) — lower and upper bounds of the intervals. Intervals can intersect. An interval can consist of a single number. 26 27 Output 28 29 Output the result of subtractions in the following format: in one line output first the number of integers in the resulting set and then the integers of the set, sorted in increasing order, separated by single space. 30 31 Examples 32 33 Input 34 35 ``` 36 2 37 1 900 38 902 999 39 ``` 40 41 Output 42 43 ``` 44 2 901 1000 45 ``` 46 47 Input 48 49 ``` 50 3 51 1 500 52 200 746 53 150 1000 54 ``` 55 56 Output 57 58 ``` 59 0 60 ```