라인업 카운팅 쿼리 1s 1024MB

Problemas

소들의 줄이 있으며, 초기 상태(즉, 시간 t=0일 때)에는 위치 0에 소 0만 있습니다 (여기서 소가 위치 k에 있다는 것은 그 소 앞에 k마리의 소가 있다는 것을 의미합니다). t=1,2,3,…인 시간 t에, 위치 0에 있는 소는 위치 ⌊t/2⌋로 이동하고, 위치 1…⌊t/2⌋에 있는 모든 소는 한 위치씩 앞으로 이동하며, 소 t는 줄의 맨 끝(위치 t)에 합류합니다.

다음과 같은 형식의 독립적인 쿼리 Q (1≤Q≤10^5)개에 답하십시오:

소 l_1…r_1 중에서, 시간 t 직후에 위치 l_2…r_2에 있는 소는 몇 마리입니까? (0≤l_1≤r_1≤t, 0≤l2≤r2≤t, t≤10^{18})

Entrada

첫 번째 줄에는 쿼리의 개수 Q가 주어집니다.

다음 Q개의 줄에는 각각 "l_1 r_1 l_2 r_2 t" 형식의 쿼리를 나타내는 다섯 개의 정수가 주어집니다.

Salida

각 쿼리에 대한 답변을 별도의 줄에 출력하세요.

Subtarea

#	Puntaje	Condición
#1	10	Q≤1000,t≤100
#2	20	모든 쿼리에 대해 l_1=r_1
#3	30	모든 쿼리에 대해 r_1≤2⋅l_1
#4	40	추가 제약 조건 없음

Ejemplo #1

4keyboard_return
0space_bar 9space_bar 0space_bar 9space_bar 9keyboard_return
3space_bar 5space_bar 4space_bar 5space_bar 9keyboard_return
4space_bar 5space_bar 3space_bar 5space_bar 9keyboard_return
1space_bar 1space_bar 3space_bar 3space_bar 9

10keyboard_return
2keyboard_return
1keyboard_return
1

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

t=9일 때, 앞에서부터 뒤까지의 소들은 [2,0,4,1,3,5,6,7,8,9]입니다.

세 번째 쿼리에 답하기 위해, 3…5번 위치에 있는 소들은

[1,3,5]이며, 이들 중 단 한 마리만이 4…5 범위에 있습니다.

Ejemplo #2

1keyboard_return
0space_bar 1000000000000000000space_bar 0space_bar 1000000000000000000space_bar 1000000000000000000

1000000000000000001

Fuente

USACO 2026 First Contest, Platinum

Debes iniciar sesión para escribir código.

#8862 upload - done - how_to_reg - call_split Subtarea

라인업 카운팅 쿼리 timer 1s memory 1024MB

Problemas translate 한국어 text_fields