35318번 - Lineup Counting Queries 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
문제
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.
예제 입력 1
4 0 9 0 9 9 3 5 4 5 9 4 5 3 5 9 1 1 3 3 9
예제 출력 1
10 2 1 1
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$.
예제 입력 2
1 0 1000000000000000000 0 1000000000000000000 1000000000000000000
예제 출력 2
1000000000000000001