| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Nikola je za svoj rođendan unatoč želji za dobrom večerom dobio lopticu. Pomalo razočaran, odlučio je taj poklon spojiti s onim prošlogodišnjim, dugačkom daskom. Shvativši da baš i ne dobiva najbolje poklone, pokušao je poboljšati ove postojeće kako bi se malo zabavio.
Svoju je dasku crtama podijelio na $L$ jednakih dijelova, a na $N$ od tih dijelova postavio je prepreke od kojih svaka na početku može, ali i ne mora biti aktivirana. Sada želi postaviti svoju lopticu na jedan dio daske na kojem se ne nalazi prepreka te ju gurnuti u jednom od dva smjera po dasci na način da ona prijeđe točno jedan dio daske po sekundi. Kad loptica dođe na dio daske na kojem se nalazi prepreka dogodit će se jedna od dvije mogućnosti ovisno o aktiviranosti prepreke:
Ako je loptica u nekoj sekundi na prvom ili zadnjem dijelu daske te je usmjerena prema rubu, ona će u sljedećoj sekundi pasti s kraja daske.
Primjer kretanja loptice:
Na početku (u 0. sekundi) loptica se nalazi na prvom dijelu daske te je usmjerena prema desno. Na drugom dijelu daske nalazi se prepreka koja nije aktivirana, a na trećem dijelu nalazi se aktivirana prepreka. Nakon jedne sekunde loptica dolazi na drugi dio. Budući da tamo prepreka nije aktivirana, loptica nastavlja dalje, a prepreka se aktivira. Nakon dvije sekunde loptica dolazi do aktivirane prepreke te se odbija od nje pa se nakon treće sekunde opet nalazi na drugom dijelu daske, a prepreka na trećem dijelu se deaktivira. Loptica se još jednom odbija te dolazi do četvrtog dijela daske nakon pet sekundi. U sljedećoj sekundi loptica će pasti s desnog ruba daske, ali to nije prikazano na slici.
Nikola se sada zapitao $Q$ pitanja, a $i$-to od njih glasi: “Ako lopticu na početku postavim na polje $A_i$ te ju usmjerim prema $B_i$, nakon koje će sekunde ona prvi puta doći na $C_i$-ti dio daske?”. Pomozi Nikoli i odgovori na njegova pitanja. Primijeti da Nikola neće zapravo gurnuti lopticu po dasci pa će prepreke za svako pitanje izgledati kao na početku, dakle pitanja su nezavisna.
U prvom su retku tri prirodna broja $L$, $N$ i $Q$ ($3 ≤ L ≤ 5 \cdot 10^8$, $1 ≤ N ≤ 2 \cdot 10^5$, $1 ≤ Q ≤ 2 \cdot 10^5$), brojevi iz teksta zadatka.
U $i$-tom od sljedećih $N$ redaka su po dva cijela broja $X_i$ i $Y_i$ ($1 ≤ X_i ≤ L$, $0 ≤ Y_i ≤ 1$). $X_i$ označava redni broj dijela daske na kojoj se nalazi $i$-ta prepreka, a $Y_i$ označava početnu aktiviranost prepreke. Ako je $Y_i$ jednak $1$, onda je $i$-ta prepreka na početku aktivirana, a inače nije. Svi $X_i$ bit će međusobno različiti.
U $i$-tom od sljedećih $Q$ redaka su po tri cijela broja $A_i$, $B_i$ i $C_i$, ($1 ≤ A_i, C_i ≤ L$, $A_i ≠ C_i$, $0 ≤ B_i ≤ 1$), brojevi iz teksta zadatka. Ako je $B_i$ jednak $0$, onda je u $i$-tom pitanju loptica usmjerena prema lijevo (prema manjim rednim brojevima dijelova daske), a inače prema desno. Na $A_i$-tom i $C_i$-tom dijelu daske neće se nalaziti prepreka.
Ispiši $Q$ redaka, odgovore na pitanja onim redom kojim su dana na ulazu. Ako u nekom pitanju loptica nikad neće doći do zadanog dijela daske, za to pitanje ispiši $-1$.
4 2 2 2 0 3 1 1 1 4 4 0 1
5 -1
3 1 2 2 0 1 1 3 3 0 1
2 2
10 4 3 1 1 10 1 3 1 7 0 2 0 9 2 1 9 8 1 2
-1 11 18
Opis prvog probnog primjera: Prepreke su postavljene kao na slici gore. Početna stanje loptice u prvom pitanju također odgovara onom na slici pa će loptica na četvrti dio daske doći nakon pet sekundi. U drugom pitanju nas zanima kada će loptica s četvrtog dijela doći na prvi ako je usmjerena prema lijevo. To se nikada neće dogoditi jer će se odbiti od prepreke na trećem dijelu te pasti s desnog ruba daske.
Opis drugog probnog primjera: U prvom pitanju će loptica doći do trećeg dijela u dvije sekunde, a prepreka će se aktivirati. U drugom pitanju prepreka opet neće biti aktivirana pa će ju i sada loptica prijeći.