Fişierul intrare/ieşire:tubeyou.in, tubeyou.outSursăAlgoritmiada 2019 Runda Maraton
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu •alexpetrescu
Timp execuţie pe test1.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tubeyou

Dupa terminarea vizualizarii unui anumit videoclip x de pe youtube (de durata durata[x] secunde), urmeaza, dupa K secunde, conform recomandarilor, vizualizarea unui videoclip next[x]. Doar ca nu esti pe youtube, ci pe un site care are sistemul de recomandari prost facut.

Cerinta

Se dau Q operatii ce trebuie procesate in ordine:

  • update vizionare videoclip: Se da un numar x, indicele unui videoclip pe care il vizitezi. Acum, toate videoclipurile y care il aveau pe x ca recomandare urmatoare (next[y] == x), isi schimba recomandarea in videoclipul recomandat pentru x (next[y] devine next[x]).
  • query Marcel iti pune o intrebare pur statistica: Se dau doua numere a si b. Deschizi simultan in doua taburi videoclipurile a si b. Marcel te intreaba in cat timp incepe un videoclip pe unul din taburi care a mai inceput pe celalalt tab. In particular, daca a == b, raspunsul e 0. Intrebarea e statistica iar desfasurarea actiunii e pur ipotetica, adica nu au loc si update-urile corespunzatoare vizualizarii videoclipurilor (sirul next[i] nu se schimba nici pe parcursul, nici in urma query-ului)

Date de intrare

Fişierul de intrare tubeyou.in contine numarul N de videoclipuri, numarul K de secunde intre finalizarea unui videoclip si inceperea urmatorului, si numarul Q de operatii pe prima linie, despartitie prin cate un spatiu. Pe urmatoare line sunt cele N numere, next[i], despartite prin cate un spatiu. Pe urmatoarea linie sunt N numere durata[i] despartite prin cate un spatiu. Pe urmatoarele Q linii, se vor gasi mai multe numere, incepand cu numarul t, care poate fi 0 sau 1. Daca t este 0, urmeaza un singur numar x, si se efectueaza o operatie de update cu parametrul x. Daca, in schimb, t este 1, urmeaza doua numere a si b, si se efectueaza o operatie de query cu parametrii a si b.

Date de ieşire

În fişierul de ieşire tubeyou.out se vor afla mai multe linii. Pe fiecare linie se va afla raspunsul pentru fiecare query, in ordinea in care apar in input. Daca raspunsul la intrebare este infinit, se va afisa numarul 1018, ca in exemplu.

Restricţii

  • 1 ≤ next[i], a, b, x ≤ N
  • 0 ≤ K ≤ 109
  • 1 ≤ durata[i] ≤ 109
  • 1 ≤ N, Q ≤ 250.000
  • Pentru 10 de puncte, 1 ≤ N, Q ≤ 1.000 - feedback testul 1
  • Pentru alte 45 de puncte, 1 ≤ N, Q ≤ 50.000 - feedback testele 3, 7, 10
  • Restul testelor de feedback fac parte din testele cele mai mari

Exemplu

tubeyou.intubeyou.out
32 0 54
3 14 20 23 4 4 4 2 8 8 10 10 12 19 25 25 27 17 24 24 23 15 14 2 22 17 16 17 22 15 31 31
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 7
1 9 14
1 21 13
1 12 9
1 20 8
1 5 6
1 23 19
1 6 11
1 10 3
1 2 4
1 11 13
1 21 5
1 24 14
1 29 30
1 18 26
1 28 16
1 16 30
1 27 22
1 28 29
1 30 25
1 15 17
1 31 31
1 31 32
1 32 10
0 4
0 24
0 14
0 27
0 31
0 32
1 7 1
1 14 9
1 13 21
1 9 12
1 8 20
1 6 5
1 19 23
1 11 6
1 3 10
1 4 2
1 13 11
1 5 21
1 14 24
1 30 29
1 26 18
1 16 28
1 30 16
1 22 27
1 29 28
1 25 30
1 17 15
1 31 31
1 32 31
1 10 32
5
3
5
2
2
1
2
4
3
2
2
2
2
2
1
3
2
2
4
2
3
0
1
1000000000000000000
3
2
4
2
1
1
1
3
2
2
2
1
2
2
1
2
2
2
3
2
2
0
1
1000000000000000000
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?