1883D.md (1851B)
1 Source: https://codeforces.com/problemset/problem/1883/D 2 3 D. In Love 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 Initially, you have an empty multiset of segments. You need to process $q$ operations of two types: 22 23 * $+$ $l$ $r$ — Add the segment $(l, r)$ to the multiset, 24 * $-$ $l$ $r$ — Remove exactly one segment $(l, r)$ from the multiset. It is guaranteed that this segment exists in the multiset. 25 26 After each operation, you need to determine if there exists a pair of segments in the multiset that do not intersect. A pair of segments $(l, r)$ and $(a, b)$ do not intersect if there does not exist a point $x$ such that $l \leq x \leq r$ and $a \leq x \leq b$. 27 28 Input 29 30 The first line of each test case contains an integer $q$ ($1 \leq q \leq 10^5$) — the number of operations. 31 32 The next $q$ lines describe two types of operations. If it is an addition operation, it is given in the format $+$ $l$ $r$. If it is a deletion operation, it is given in the format $-$ $l$ $r$ ($1 \leq l \leq r \leq 10^9$). 33 34 Output 35 36 After each operation, print "YES" if there exists a pair of segments in the multiset that do not intersect, and "NO" otherwise. 37 38 You can print the answer in any case (uppercase or lowercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers. 39 40 Example 41 42 Input 43 44 ``` 45 12 46 47 + 1 2 48 49 + 3 4 50 51 + 2 3 52 53 + 2 2 54 55 + 3 4 56 57 - 3 4 58 59 - 3 4 60 61 - 1 2 62 63 + 3 4 64 65 - 2 2 66 67 - 2 3 68 69 - 3 4 70 ``` 71 72 Output 73 74 ``` 75 NO 76 YES 77 YES 78 YES 79 YES 80 YES 81 NO 82 NO 83 YES 84 NO 85 NO 86 NO 87 ``` 88 89 Note 90 91 In the example, after the second, third, fourth, and fifth operations, there exists a pair of segments $(1, 2)$ and $(3, 4)$ that do not intersect. 92 93 Then we remove exactly one segment $(3, 4)$, and by that time we had two segments. Therefore, the answer after this operation also exists.