DMOPC '17 Contest 5 P2 - Mimi and Binary - DMOJ: Modern Online Judge

DMOPC '17 Contest 5 P2 - Mimi and Binary

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

Problem type

Mimi is playing with a string $S$ $S$ , consisting of only 0s and 1s. Her little sister comes along and being very curious, asks $Q$ $Q$ questions about the binary string:

If we consider the substring starting from the $x_i$ $x_{i}$ th index, what is the leftmost index such that there are $y_i$ $y_{i}$ occurrences of the digit $z_i$ $z_{i}$ ?

Help Mimi write a program to answer these queries.

Constraints

Let $|S|$ $| S |$ denote the length of string $S$ $S$ .

For all subtasks:

$1 \le x_i, y_i \le |S|$ $1 \leq x_{i}, y_{i} \leq | S |$

$0 \le z_i \le 1$ $0 \leq z_{i} \leq 1$

Subtask 1 [20%]

$1 \le |S|, Q \le 1\,000$ $1 \leq | S |, Q \leq 1 000$

Subtask 2 [80%]

$1 \le |S|, Q \le 200\,000$ $1 \leq | S |, Q \leq 200 000$

Input Specification

The first line will contain the string $S$ $S$ .
The next line of input will contain a single integer, $Q$ $Q$ .
The next $Q$ $Q$ lines will each contain three space-separated integers: $x_i$ $x_{i}$ , $y_i$ $y_{i}$ , and $z_i$ $z_{i}$ , the $i$ $i$ th query.

Output Specification

The output should contain $Q$ $Q$ integers, each on a new line. The $i$ $i$ th integer should be either the leftmost index such that there are $y_i$ $y_{i}$ occurrences of the digit $z_i$ $z_{i}$ , or -1 if no such index exists.

Sample Input

Copy

Sample Output

Copy

3
4
-1

Comments

5

Medi commented on Nov. 14, 2018, 6:51 a.m.

Could someone explain the sample input and output?

6

kingW3 commented on Nov. 14, 2018, 1:20 p.m. ← edited →

For the first query the substring $010$ $010$ is the first to have $2$ $2$ occurrences of $0$ $0$ so the answer is $3$ $3$ , the second query the substring $0101$ $0101$ is the first to have $2$ $2$ occurrences of $1$ $1$ hence the answer is $4$ $4$ and for the last there is no substring containing $3$ $3$ ones starting from first char.

64

echofox commented on March 28, 2018, 12:28 a.m. ← edited →

don't you just hate it when you're doing something and your younger sibling comes over and asks "if we consider the substring starting from the $x_i$ $x_{i}$ th index, what is the leftmost index such that there are $y_i$ $y_{i}$ occurrences of the digit $z_i$ $z_{i}$ ?"

12

GeeTranzit commented on Jan. 27, 2020, 2:45 p.m.

relatable