P14984 [USACO26JAN1] Lineup Counting Queries P

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 $\lfloor t/2\rfloor$, every cow in positions $1\dots \lfloor t/2\rfloor$ moves forward one position, and cow $t$ joins the line at the end of the line (position $t$). Answer $Q$ ($1\le Q\le 10^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\le l_1\le r_1\le t, 0\le l_2\le r_2 \le t, t\le 10^{18}$)

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 the answer to each query on a separate line.

Lineups at various times: ```none 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$. --- - Input 3: $Q\le 1000, t\le 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.