Lineup Counting Queries
다이아몬드 III의견: 0
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}\))
Problem credits: Agastya Goel and Benjamin Qi
SCORING
- 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
Problem credits: Agastya Goel and Benjamin Qi
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.
4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 910
2
1
1Lineups 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\).
1
0 1000000000000000000 0 1000000000000000000 10000000000000000001000000000000000001riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Platinum
평가 및 의견
Lineup Counting Queries
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Lineup Counting Queries