Fişierul intrare/ieşire:queries.in, queries.outSursăACM-ICPC Faza Nationala 2017
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test4.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Queries

Hei, ia uite, esti in comisie din nou. Nu-ti place sa fii in comisie. E stresant, iar oamenii iti adreseaza injuraturi, injuraturile devin hashtaguri, popelile devin meme-uri. Ce viata.

Toata comisia este de acord ca in fiecare an e nevoie de o problema 100% clasica. Tu nici nu mai tii minte ce parere ai despre asta. Cert e ca ti s-a dat sa faci testele pentru urmatoarea problema:

<Vi se da un sir de N numere si M query-uri de forma "care este valoarea maxima din subsecventa [x, y]?". Raspundeti la query-uri cu un RMQ.>

Munca pentru pregatirea acestei probleme a fost paralelizata (more like paralizata, am I right?) in urmatorul fel: o persoana construieste secventa de numere. O alta persoana decide numarul de query-uri si raspunsurile acestora. Iar tu alegi efectiv query-urile pentru care se obtin aceste raspunsuri. Inteligent, nu?

Fiindca nu vrei sa intre cele mai nefericite bruturi, iti doresti ca suma lungimilor query-urilor pe care le propui sa fie maxim posibila. De-asemenea, fiindca exista pe lume oameni care memoizeaza si la genul asta de probleme, iti doresti ca toate query-urile sa fie distincte.

Date de intrare

Fişierul de intrare queries.in va contine pe prima sa linie numarul T, reprezentand numarul de teste. Structura unui test este urmatoarea: pe prima linie se afla numerele N M, reprezentand numarul de numere din sir, respectiv numarul de query-uri pe care le vei crea. Urmeaza o linie cu N numere, reprezentand valorile din sir. Apoi urmeaza o linie de M numere, reprezentand raspunsurile pe care trebuie sa le produca aceste query-uri.

Date de ieşire

În fişierul de ieşire queries.out se vor afla T linii, fiecare continand un singur numar intreg, reprezentand lungimea totala maxim posibila a unor query-uri care respecta conditiile din input. In caz ca un asemenea set de query-uri nu exista, vei afisa -1 si iti vei trata colegii cu si mai putin respect.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 105
  • 1 ≤ valorile din sir ≤ 109

Exemplu

queries.inqueries.out
2
5 3
1 2 5 2 1
5 5 5
3 4
5 3 2
5 5 5 5
13
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?