codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.