codeforces-scrape

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

2244E.md (2241B)


      1 Source: https://codeforces.com/problemset/problem/2244/E
      2 
      3 E. Masha and the Garland
      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 Masha has a New Year garland consisting of $n$ bulbs. Each bulb can be either off or on. The state of the garland is given by a binary string $s$ of length $n$, where '0' denotes an off bulb and '1' denotes an on bulb.
     22 
     23 Masha considers the garland beautiful if the states of adjacent bulbs strictly alternate. That is, there are no two adjacent bulbs that are both on or both off. For example, the garlands '01010' and '1010' are beautiful, while '0110' and '000' are not.
     24 
     25 Yura can apply the following operation to the garland: choose a subsegment and flip the state of all bulbs in it, that is, turn all on bulbs off and all off bulbs on.
     26 
     27 Masha invites him to play the following game $q$ times: she chooses a segment from the $l$-th to the $r$-th bulb inclusive, and Yura must make this segment beautiful using at most $k$ operations.
     28 
     29 However, Yura is not sure whether this is always possible, so he asks you to determine for each game whether he can make the chosen segment beautiful using no more than $k$ operations. Note that the games are independent, and the garland itself is not actually modified.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of the garland and the number of games.
     36 
     37 The second line contains a binary string $s$ of length $n$, consisting only of characters '0' and '1'.
     38 
     39 The next $q$ lines each contain three integers $l$, $r$, and $k$ ($1 \le l \le r \le n$, $0 \le k \le n$) — the boundaries of the segment and the maximum allowed number of operations.
     40 
     41 It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each game, output "YES" if the segment can be made beautiful using at most $k$ operations, and "NO" otherwise.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 2
     53 
     54 5 5
     55 
     56 00110
     57 
     58 1 5 1
     59 
     60 1 5 2
     61 
     62 2 4 1
     63 
     64 1 2 0
     65 
     66 3 4 0
     67 
     68 4 2
     69 
     70 1010
     71 
     72 1 4 0
     73 
     74 2 3 1
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 YES
     81 
     82 YES
     83 
     84 YES
     85 
     86 NO
     87 
     88 NO
     89 
     90 YES
     91 
     92 YES
     93 ```