| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 21 | 4 | 4 | 50.000% |
Ona je nosila u rukama odvratno, uznemiravajuće žuto cvijeće. Ipak, svidjela mu se.
Prema poznatom teoremu, osobnost svake osobe može se prikazati permutacijom duljine $N$. Tako se i osobnost našeg junaka, Majstora, može prikazati permutacijom $p$. A osobnost Margarite, dame koja mu je zapala za oko, može se prikazati permutacijom $q$.
Mjerilo za sličnost permutacija, a time i sreću u bračnom životu, može se prikazati kao najveća veličina presjeka nekog podintervala duljine $K$ permutacije $p$ te podintervala duljine $K$ permutacije $q$. Pri tome, presjek se promatra u skupovnom smislu, tj. nije bitan poredak brojeva u podintervalima. Primjerice, u slučaju $N = 4,ドル $K = 3,ドル sličnost permutacija $(2,4円,1円,3円)$ te $(1,2円,3円,4円)$ je 2ドル$ i ona se postiže za bilo koji izbor podintervala.
Otkada je vidio Margaritu, Majstor je opsjednut sličnošću svoje i njezine permutacije, te je njegova osobnost postala veoma promjenjiva. Tako svakog dana, u njegovoj će se permutaciji zamijeniti dva susjedna elementa. Napomenimo da je ta promjena stalna tj. ta dva elementa ostaju zamijenjena tijekom sljedećih dana. Sada ga zanima sličnost njegove i njezine permutacije kad ju je tek ugledao, te sličnost nakon promjene tijekom sljedećih $Q$ dana. Dodatno, zanima ga i za koliko se parova podintervala postiže tolika sličnost. U svojim ljubavnim jadima, zamolio Vas je za pomoć!
U prvom su retku brojevi $N,ドル $K$ i $Q$.
U drugom se retku nalazi $N$ brojeva gdje $i$-ti označava $p_i$.
U trećem se retku nalazi $N$ brojeva gdje $j$-ti označava $q_j$.
U sljedećih $Q$ redaka nalaze se opisi promjena. U $i$-tom se retku nalazi broj $t_i$ (1ドル ≤ t_i < N$) koji označava da su se u Majstorovoj permutaciji $p$ zamijenili brojevi na pozicijama $t_i$ i $t_i + 1$.
U prvi redak potrebno je ispisati početnu sličnost permutacija i broj parova podintervala za koje se ta sličnost postiže.
U sljedećih $Q$ redaka potrebno je ispisati isto, nakon promjene toga dana.
U svim podzadacima vrijedi 2ドル ≤ N ≤ 100,000円,ドル 1ドル ≤ K ≤ N$ i 0ドル ≤ Q ≤ 100,000円$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $Q = 0,ドル $N ≤ 100$ |
| 2 | 10 | $Q = 0,ドル $N ≤ 5000$ |
| 3 | 33 | $Q = 0$ |
| 4 | 7 | $N, Q ≤ 100$ |
| 5 | 10 | $N, Q ≤ 5000$ |
| 6 | 33 | Nema dodatnih ograničenja. |
2 1 1 1 2 1 2 1
1 2 1 2
4 3 0 2 4 1 3 1 2 3 4
2 4
5 3 3 1 4 3 2 5 4 5 1 2 3 3 1 4
2 5 2 6 3 1 3 1
Pojašnjenje drugog probnog primjera:
Podintervali duljine tri u prvoj permutaciji su $(2,4円,1円)$ i $(4,1円,3円),ドル a u drugoj $(1,2円,3円)$ i $(2,3円,4円)$. Za presjeke imamo:
$$\{2, 4, 1\} ∩ \{1, 2, 3\} = \{1, 2\}, \{2, 4, 1\} ∩ \{2, 3, 4\} = \{2, 4\},$$ $$\{4, 1, 3\} ∩ \{1, 2, 3\} = \{1, 3\}, \{4, 1, 3\} ∩ \{2, 3, 4\} = \{3, 4\},$$
pa vidimo da sličnost iznosi 2 te da se postiže za četiri para podintervala.
Olympiad > Croatian Highschool Competitions in Informatics > 2023 > Croatian Olympiad in Informatics 2023 4번