Bitmask Magic

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

As the Supreme Overdeity of Informatics of the William Collegiate Institute, Allan has now been selected to give a lesson on bitmasks and their operations. While he was creating his lesson plan, he came up with the following question:

You're given the numbers Q, L, R and Q queries (q_1, x_1), (q_2, x_2), \dots, (q_Q, x_Q). For each query (q_i, x_i), he wants you to find the minimum number of operations to transform it from q_i to any integer in the range [L, \min(q_i + x_i, R)] (or -1 if it's impossible). A single operation is defined as inserting a 0 or 1 at any position in the binary representation of an integer.

Here are some examples (note that the digit in square brackets is the newly inserted one):

  • 100 -> 10[1]0: 4 \to 10
  • 100 -> [1]100: 4 \to 12
  • 100 -> 100[1]: 4 \to 9

Important note: leading 0s are not counted.

As you want to prove to Allan that you are the true Supreme Overdeity of Informatics at WCI, you've decided to attempt the question.

Constraints

For all subtasks:

1 \le Q \le 4 \times 10^6

1 \le L \le R \le 5 \times 10^5

1 \le q_i, x_i \le 5 \times 10^5

Subtask 1 [20%]

L = R

x_i = 5 \times 10^5

1 \le Q \le 10^4

Subtask 2 [25%]

x_i = 5 \times 10^5

Subtask 3 [55%]

No additional constraints.

Input Specification

The first line contains the integers Q, L, R.

The next Q lines contain the queries (q_1, x_1), (q_2, x_2), \dots, (q_Q, x_Q) with 1 query per line.

Output Specification

Output the answer to each query on its own line.

Sample Input

6 17 17
5 100
5 11
10 7
8 9
17 1
1 17

Sample Output

2
-1
-1
1
0
4

Sample Explanation

Here are the bitmask representations of the queries (the bits in brackets represent the added bits):

  • 101 -> 1[00]01: 5 \to 17
  • 17-5 > 11 so this query is impossible.
  • 10 is 1010 in binary and 17 is 10001 in binary. It can be shown that this query is impossible to complete.
  • 1000 -> 1000[1]: 8 \to 17
  • 10001 -> 10001: 17 \to 17
  • 1 -> [1000]1: 1 \to 17

Comments

There are no comments at the moment.