레이팅 미적용소들이 한 줄로 서 있는데, 처음(즉, 시각 \(t = 0\))에는 소 \(0\)만이 위치 \(0\)에 서 있다 (여기서 어떤 소의 앞에 소가 \(k\)마리 있으면 그 소는 위치 \(k\)에 있다고 한다). 시각 \(t\) (\(t=1,2,3,\dots\))에, 위치 0에 있는 소는 위치 \(\lfloor t/2\rfloor\)로 이동하고, 위치 \(1\dots \lfloor t/2\rfloor\)에 있는 모든 소는 한 위치 앞으로 이동하며, 소 \(t\)가 줄의 맨 끝(위치 \(t\))에 합류한다.
다음 형태의 \(Q\) (\(1\le Q\le 10^5\))개의 독립적인 쿼리에 답하라.
- 소 \(l_1\dots r_1\) 중, 시각 \(t\) 직후에 위치 \(l_2\dots r_2\)에 있는 소는 몇 마리인가? (\(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
- 입력 3: \(Q\le 1000, t\le 100\)
- 입력 4-7: 모든 쿼리에서 \(l_1 = r_1\)
- 입력 8-14: 모든 쿼리에서 \(r_1 \leq 2 \cdot l_1\)
- 입력 15-21: 추가 제약 없음
Problem credits: Agastya Goel and Benjamin Qi
첫째 줄에 쿼리의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 "\(l_1\) \(r_1\) \(l_2\) \(r_2\) \(t\)" 형태의 쿼리를 지정하는 다섯 정수가 주어진다.
각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.
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