Fişierul intrare/ieşire:mediana.in, mediana.outSursăFinala ONIS 2016
AutorCosmin-Mihai TutunaruAdăugată destocarulCosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test1.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mediana

Se dau doua siruri ( A si B ) sortate crescator de lungime N si M. Curios din fire, Algorel, in internship la AlgoTech, trebuie sa afle raspunsul la mai multe intrebari de forma: daca s-ar interclasa secventa [ le1; ri1 ] din sirul A cu secventa [ le2; ri2 ] din sirul B obtinandu-se astfel un alt sir crescator, care este elementul ce se afla pe pozitia din mijloc din sirul ce se obtine?

Dupa ce Algorel a rezolvat problema si a vazut cat este de interesanta, s-a decis sa o propuna la un concurs de algoritmica. Cum ONIS are loc la Cluj anul acesta, voi sunteti norocosii care trebuie sa o rezolve!

Dându-se T teste, fiecare avand doua siruri A si B cu N respectiv M elemente sortate, sa se raspunda la Q intrebari de forma celei explicate mai sus.

Date de intrare

Fişierul de intrare mediana.in conţine pe prima linie numărul T, iar pe urmatoarele linii sunt descrise cele T teste. Fiecare test ocupa mai multe linii, in felul urmator:

  • O linie avand valorile N, M si Q
  • O linie avand N numere resprezentand sirul A
  • O linie avand M numere reprezentand sirul B
  • Q linii avand cate 4 valori: le1, ri1, le2, ri2

Date de ieşire

În fişierul de ieşire mediana.out trebuie sa afisati mai multe linii. Pe fiecare linie se afla un singur numar, reprezentand raspunsul la cate o intrebare din fisierul de intrare. Raspunsurile trebuie sa apara in ordinea intrebarilor din fisierul de intrare.

Restricţii

  • T <= 20
  • 1 <= N, M, Q <= 100.000
  • 0 <= le1 <= ri1 < N
  • 0 <= le2 <= ri2 < M
  • Toate numerele din fisierul de intrare sunt mai mici de 2 miliarde
  • In cazul in care L - lungimea sirului este para, elementul din mijloc se va considera cel de pe pozitia L div 2 (partea intreaga)

Exemplu

mediana.inmediana.out
2
5 5 8
1 2 3 4 5
1 2 3 4 5
0 0 1 4
0 1 2 4
0 2 3 4
0 3 4 4
1 4 0 0
2 4 0 1
3 4 0 2
4 4 0 3
8 7 4
1 3 6 6 7 9 13 31
2 3 4 5 6 7 8
0 7 0 6
3 5 1 3
2 4 3 6
5 7 1 6
3
3
3
3
3
3
3
3
6
5
6
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?