| Fişierul intrare/ieşire: | towers.in, towers.out | Sursă | Shumen 2016 - Seniori |
| Autor | Rusko Shikov | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Towers
Orasul X este compus din N blocuri, ordonate sub forma unei secvente numerotate de la 1 la N, de la vest la est. Fiecare bloc are o inaltime diferita - un numar intreg, respectiv h1, h2, ..., hN. Guvernul planuieste sa construiasca un turn, stiuat in aceeasi secventa cu blocurile (poate sa fie inaintea primului bloc, intre oricare doua blocuri sau dupa ultimul bloc). Turnul o sa transmita mesaje cetatenilor. Turnul trebuie sa aiba inaltimea H, care trebuie sa fie diferita de toate celelalte inaltimi ale blocurilor.
Din cauza unor idei ingineresti destul de ciudate, turnul va putea transmite semnale doar catre vest (spre inceputul secventei de blocuri). Semnalele sunt de asemenea ciudate - acestea sunt unde care traverseaza orizontal (parelele cu solul, pe care le consideram linii drepte) si sunt emise din toata suprafata blocului (de sus in jos). Deci, ne putem imagina ca turnul emite o banda continua de semnale cu latimea egala cu inaltimea turnului. Cand o unda intalneste un bloc, se opreste. Fiecare bloc primeste semnalele semnalele folosind un receptor localizat in varful acestuia. Un bloc primeste un mesaj daca cel putin o unda atinge receptorul.
Cu alte cuvinte, blocul cu indicele i va primi mesaje de la turn doar atunci cand: blocul i este situat in stanga turnului; i nu este mai inalt decat turnul si nu exista un alt bloc j intre ele (j > i), care este mai inalt decat blocul i.
Uitati-va la exemplul din figura alaturata: blocurile care receptioneaza mesaje sunt cele cu indicii 2, 5, 6, 9.
Un singur turn o sa fie construit, cu toate acestea guvernul a primit oferte pentru K variante de turnuri, fiecare avend o inaltime diferita. Ofertele de turnuri sunt numerotate de la 1 la K. Fiecare turn are inaltimea sa, care este de asemenea diferita de inaltimea blocurilor. Liderii orasului doresc sa afle numarul maxim de blocuri, care ar primi mesajele, pentru fiecare dintre cele K oferte de turnuri, inainte de a lua decizia oficiala. Desigur, raspunsurile trebuie determinate considerand asezarea optima a fiecarui turn.
Sa se determine numarul maxim de blocuri care ar primi mesaje pentru fiecare din cele K oferte, date fiind secventa de blocuri din oras (mai exact, inaltimile lor) si inaltimile tuturor ofertelor de turnuri.
Date de intrare
Pe prima linie a fişierului de intrare towers.in se gasesc doua numere naturale separate printr-un spatiu: N si K - numarul de blocuri si numarul de oferte de turnuri.
Pe cea de a doua linie se gasesc N numere naturale separate prin spatii - inaltimile blocurilor din oras, numerotate de la 1 la N.
Pe cea de a treia linie se gasesc K numere naturale separate prin spatii - inaltimile ofertelor de turnuri.
Date de ieşire
Programul trebuie sa afiseze o singura linie in fişierul de ieşire towers.out: K numere naturale separate prin cate un spatiu: pentru fiecare oferta din cea de a treia linie din input - numarul maxim de blocuri care ar primi mesaje, daca turnul ar fi construit si plasat optim.
Restricţii
- 1 ≤ N ≤ 1 000 000
- 1 ≤ K ≤ 1 000 000
- 1 ≤ inaltimea fiecarui bloc si oferte de turnuri ≤ 109
- Pentru 20% din teste N ≤ 1000, K ≤ 20
- Pentru alte 30% din teste N ≤ 1 000 000, K ≤ 20
Exemplu
| towers.in | towers.out |
|---|---|
| 16 3 200 170 155 90 150 140 40 30 185 160 50 110 80 15 70 35 165 180 120 | 5 6 4 |
Nota
A se observa ca in imaginea de mai sus inaltimile turnurilor 3 si 5 sunt inversate, fapt semnalat de catre comisie in timpul concursului.
