Lineup Counting Queries

There is a line of cows, initially (i.e. at time $t = 0$ ) containing only cow $0$ at position $0$ (here, a cow is at position $k$ if there are $k$ cows in front of it). At time $t$ for $t = 1, 2, 3, \dots$ , the cow at position 0 moves to position $⌊ t /2 ⌋$ , every cow in positions $1 \dots ⌊ t /2 ⌋$ moves forward one position, and cow $t$ joins the line at the end of the line (position $t$ ).

Answer $Q$ ( $1 \leq Q \leq 1 0^{5}$ ) independent queries each of the following form:

Out of cows $l_{1} \dots r_{1}$ , how many are located at positions $l_{2} \dots r_{2}$ immediately after time $t$ ? ( $0 \leq l_{1} \leq r_{1} \leq t, 0 \leq l_{2} \leq r_{2} \leq t, t \leq 1 0^{18}$ )

Lineups at various times:

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

At $t = 9$ the cows from front to back are $[2, 0, 4, 1, 3, 5, 6, 7, 8, 9]$ .

To answer the third query, the cows at positions $3 \dots 5$ are $[1, 3, 5]$ , and only one of them is in the range $4 \dots 5$ .

SCORING:

Input 3: $Q \leq 1000, t \leq 100$
Inputs 4-7: $l_{1} = r_{1}$ for all queries
Inputs 8-14: $r_{1} \leq 2 \cdot l_{1}$ for all queries
Inputs 15-21: No additional constraints

Problem credits: Agastya Goel and Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $Q$ , the number of queries.

The next $Q$ lines each contain five integers specifying a query of the form " $l_{1}$ $r_{1}$ $l_{2}$ $r_{2}$ $t$ ."

Output Format

Output the answer to each query on a separate line.

Sample Input 1

4 0 9 0 9 9 3 5 4 5 9 4 5 3 5 9 1 1 3 3 9

Sample Output 1

10 2 1 1

Sample Input 2

1 0 1000000000000000000 0 1000000000000000000 1000000000000000000

Sample Output 2

1000000000000000001

Submit

Language