Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mediana.in, mediana.out | Sursă | Finala ONIS 2016 |
| Autor | Cosmin-Mihai Tutunaru | Adăugată de |  Cosmin-Mihai Tutunaru •stocarul |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mediana
Se dau doua siruri ( A si B ) sortate crescator de lungime N si M. Curios din fire, Algorel ar vrea 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?
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
Exemplu
| mediana.in | mediana.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
