codeforces-scrape

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

1840E.md (4245B)


      1 Source: https://codeforces.com/problemset/problem/1840/E
      2 
      3 E. Character Blocking
      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 two strings of equal length $s_1$ and $s_2$, consisting of lowercase Latin letters, and an integer $t$.
     22 
     23 You need to answer $q$ queries, numbered from $1$ to $q$. The $i$-th query comes in the $i$-th second of time. Each query is one of three types:
     24 
     25 * block the characters at position $pos$ (indexed from $1$) in both strings for $t$ seconds;
     26 * swap two unblocked characters;
     27 * determine if the two strings are equal at the time of the query, ignoring blocked characters.
     28 
     29 Note that in queries of the second type, the characters being swapped can be from the same string or from $s_1$ and $s_2$.
     30 
     31 Input
     32 
     33 The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.
     34 
     35 Then follow the descriptions of the test cases.
     36 
     37 The first line of each test case contains a string $s_1$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$).
     38 
     39 The second line of each test case contains a string $s_2$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$).
     40 
     41 The strings have equal length.
     42 
     43 The third line of each test case contains two integers $t$ and $q$ ($1 \le t, q \le 2 \cdot 10^5$). The number $t$ indicates the number of seconds for which a character is blocked. The number $q$ corresponds to the number of queries.
     44 
     45 Each of the next $q$ lines of each test case contains a single query. Each query is one of three types:
     46 
     47 * "$1\ \ \ pos$" — block the characters at position $pos$ in both strings for $t$ seconds;
     48 * "$2\ \ \ 1/\;\!2\ \ \ pos_1\ \ \ 1/\;\!2\ \ \ pos_2$" — swap two unblocked characters. The second number in the query indicates the number of the string from which the first character for the swap is taken. The third number in the query indicates the position in that string of that character. The fourth number in the query indicates the number of the string from which the second character for the swap is taken. The fifth number in the query indicates the position in that string of that character;
     49 * "$3$" — determine if the two strings are equal at the time of the query, ignoring blocked characters.
     50 
     51 For queries of the first type, it is guaranteed that at the time of the query, the characters at position $pos$ are not blocked.
     52 
     53 For queries of the second type, it is guaranteed that the characters being swapped are not blocked.
     54 
     55 All values of $pos, pos_1, pos_2$ are in the range from $1$ to the length of the strings.
     56 
     57 The sum of the values of $q$ over all test cases, as well as the total length of the strings $s_1$, does not exceed $2 \cdot 10^5$.
     58 
     59 Output
     60 
     61 For each query of the third type, output "YES" if the two strings $s_1$ and $s_2$ are equal at the time of the query, ignoring blocked characters, and "NO" otherwise.
     62 
     63 You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be accepted as a positive answer.
     64 
     65 Example
     66 
     67 Input
     68 
     69 ```
     70 2
     71 
     72 codeforces
     73 
     74 codeblocks
     75 
     76 5 7
     77 
     78 3
     79 
     80 1 5
     81 
     82 1 6
     83 
     84 1 7
     85 
     86 1 9
     87 
     88 3
     89 
     90 3
     91 
     92 cool
     93 
     94 club
     95 
     96 2 5
     97 
     98 2 1 2 2 3
     99 
    100 2 2 2 2 4
    101 
    102 1 2
    103 
    104 3
    105 
    106 3
    107 ```
    108 
    109 Output
    110 
    111 ```
    112 NO
    113 YES
    114 NO
    115 YES
    116 NO
    117 ```
    118 
    119 Note
    120 
    121 Let's look at the strings $s_1$ and $s_2$ after each of the $q$ queries. Blocked characters will be denoted in red.
    122 
    123 First example input:
    124 
    125 ($codeforces$, $codeblocks$) $\rightarrow$ ($codeforces$, $codeblocks$) $\rightarrow$ ($code\color{red}{f}orces$, $code\color{red}{b}locks$) $\rightarrow$ ($code\color{red}{fo}rces$, $code\color{red}{bl}ocks$) $\rightarrow$ ($code\color{red}{for}ces$, $code\color{red}{blo}cks$) $\rightarrow$ ($code\color{red}{for}c\color{red}{e}s$, $code\color{red}{blo}c\color{red}{k}s$) $\rightarrow$ ($code\color{red}{for}c\color{red}{e}s$, $code\color{red}{blo}c\color{red}{k}s$) $\rightarrow$ ($codef\color{red}{or}c\color{red}{e}s$, $codeb\color{red}{lo}c\color{red}{k}s$)
    126 
    127 Second example input:
    128 
    129 ($cool$, $club$) $\rightarrow$ ($cuol$, $clob$) $\rightarrow$ ($cuol$, $cbol$) $\rightarrow$ ($c\color{red}{u}ol$, $c\color{red}{b}ol$) $\rightarrow$ ($c\color{red}{u}ol$, $c\color{red}{b}ol$) $\rightarrow$ ($cuol$, $cbol$)