DMOPC '17 Contest 5 P2 - Mimi and Binary - Olympiads 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 \le x_i, y_i \le |S|~

$0 \le z_i \le 1$ ~0 \le z_i \le 1~

Subtask 1 [20%]

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

Subtask 2 [80%]

$1 \le |S|, Q \le 200\,000$ ~1 \le |S|, Q \le 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

Sample Output

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