| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 34 | 3 | 3 | 11.538% |
Zadano je $N$ kvadrata koji su označeni brojevima od 1ドル$ do $N$. Kvadrat s oznakom $i$ ima duljinu stranice $a_i,ドル gdje je $a_i$ neki paran broj. Na početku je svaki kvadrat obojan u crnu boju.
Jura kod sebe ima koordinatni sustav $i$ odlučio je iskoristiti $N - 1$ sekundi svog života da bi se malo pozabavio sa zadanim kvadratima. U $i$-toj sekundi Jura je uzeo kvadrate s oznakama $x_i$ i $y_i$ te ih spojio u novi kvadrat s oznakom $n + i$ (nakon spajanja kvadrati s oznakama $x_i$ i $y_i$ više ne postoje).
Prilikom spajanja dva kvadrata, Jura ih postavi u koordinatni sustav tako da su im središta u koordinatama $(0, 0)$ te da su im stranice paralelne s osima. Novi kvadrat bit će dimenzija kao veći od dva koja se spajaju, a bit će obojan na sljedeći način: ako je neka točka u oba kvadrata crna ili u oba bijela, u novom kvadratu bit će bijela, a inače će biti crna.
Spajanja, naravno, nisu besplatna, cijena spajanja jednaka je površini svih točaka koje su crne u oba kvadrata istovremeno. Juru zanima kolika je cijena svakog od $N - 1$ spajanja koje je napravio. Slike prikazuju primjere spajanja.
U prvom je retku prirodni broj $N,ドル broj kvadrata.
U drugom je retku niz prirodnih brojeva $a_1, a_2, \dots , a_N$ koji predstavlja duljine stranica zadanih kvadrata.
U sljedećih $N - 1$ redaka nalaze se po 2ドル$ broja, u $i$-tom od tih $N - 1$ redaka nalaze se brojevi $x_i$ i $y_i,ドル oznake kvadrata koje je Jura spojio u $i$-toj sekundi.
Ispišite $N - 1$ redaka. U $i$-tom retku ispišite po jedan broj, cijenu $i$-tog spajanja.
U svim podzadacima vrijedi 1ドル ≤ N ≤ 10^5,ドル 2ドル ≤ a_i ≤ 10^6,ドル ai je paran za sve $i = 1, 2, \dots , N,ドル 1ドル ≤ x_i , y_i ≤ N + i - 1,ドル za sve $i = 1, 2, \dots , N - 1,ドル svi $x_i$ i $y_i$ međusobno su različiti.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | $N ≤ 5000$ |
| 2 | 25 | $x_1 = 1,ドル $y_1 = 2,ドル $x_i = i + 1,ドル $y_i = N + i - 1$ za sve $i = 2, 3, \dots , N-1$ |
| 3 | 17 | $N$ je potencija broja 2ドル,ドル $x_i = 2i - 1,ドル $y_i = 2i$ |
| 4 | 21 | $N ≤ 30000$ |
| 5 | 23 | Nema dodatnih ograničenja. |
6 8 6 2 4 2 6 1 2 3 4 5 7 6 8 9 10
36 4 0 12 4
7 4 2 6 6 2 4 2 1 2 3 8 4 9 5 10 6 11 7 12
4 12 24 0 16 0
8 4 10 2 10 6 8 4 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14
16 4 36 16 84 28 0
Pojašnjenje prvog probnog primjera:
Posljednje spajanje prikazano je na slici: