codeforces-scrape

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

2036C.md (2020B)


      1 Source: https://codeforces.com/problemset/problem/2036/C
      2 
      3 C. Anya and 1100
      4 
      5 time limit per test
      6 
      7 3 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 While rummaging through things in a distant drawer, Anya found a beautiful string $s$ consisting only of zeros and ones.
     22 
     23 Now she wants to make it even more beautiful by performing $q$ operations on it.
     24 
     25 Each operation is described by two integers $i$ ($1 \le i \le |s|$) and $v$ ($v \in \{0, 1\}$) and means that the $i$-th character of the string is assigned the value $v$ (that is, the assignment $s_i = v$ is performed).
     26 
     27 But Anya loves the number $1100$, so after each query, she asks you to tell her whether the substring "1100" is present in her string (i.e. there exist such $1 \le i \le |s| - 3$ that $s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100}$).
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 The first line of the test case contains the string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$), consisting only of the characters "0" and "1". Here $|s|$ denotes the length of the string $s$.
     34 
     35 The next line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.
     36 
     37 The following $q$ lines contain two integers $i$ ($1 \leq i \leq |s|$) and $v$ ($v \in \{0, 1\}$), describing the query.
     38 
     39 It is guaranteed that the sum of $|s|$ across all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each query, output "YES", if "1100" is present in Anya's string; otherwise, output "NO".
     44 
     45 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 100
     55 
     56 4
     57 
     58 1 1
     59 
     60 2 0
     61 
     62 2 0
     63 
     64 3 1
     65 
     66 1100000
     67 
     68 3
     69 
     70 6 1
     71 
     72 7 1
     73 
     74 4 1
     75 
     76 111010
     77 
     78 4
     79 
     80 1 1
     81 
     82 5 0
     83 
     84 4 1
     85 
     86 5 0
     87 
     88 0100
     89 
     90 4
     91 
     92 3 1
     93 
     94 1 1
     95 
     96 2 0
     97 
     98 2 1
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 NO
    105 NO
    106 NO
    107 NO
    108 YES
    109 YES
    110 NO
    111 NO
    112 YES
    113 YES
    114 YES
    115 NO
    116 NO
    117 NO
    118 NO
    119 ```