| Fişierul intrare/ieşire: | tango2.in, tango2.out | Sursă | Lot Deva Seniori 2019, baraj 2 |
| Autor | Andrei Constantinescu | Adăugată de |  Alex Luchianov •AlexandruLuchianov1 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tango2
La o seara dansanta se afla N baieti si fete, fiecare avand pe piept cate un numar unic intre 1 si N. Ei se aranjeaza in linie, in ordinea numerelor care le sunt desemnate, la distanta de 1 metru unul de celalalt. Seara se desfasoara pe runde de tango. In cadrul fiecarei runde, organizatorii aleg o subsecventa continua(data prin capatul stang si cel drept) a celor N dansatori care sa participe la runda si:
- Daca numarul baietilor(din secventa) difera de numarul fetelor (din secventa), runda nu se danseaza;
- Daca numarul lor este identic, atunci fiecare baiat va merge sa invite cate o fata distincta la dans. Fetele vor accepta doar daca suma distantelor parcurse de baieti panal fetele alese este minima. Tangoul poate sa inceapa.
La sfarsitul fiecarei runde dansatorii isi reiau locurile.
Baietii, care spera ca aceasta seara sa fie una speciala pentru fiecare(sau cel putin pentru cat mai multi) dintre ei, va roaga ca, stiind pozitionarea initiala a dansatorilor, sa determinati pentru fiecare runda daca aceasta poate fi dansata, si, in caz afirmativ, care este suma distantelor parcuse de ei(exprimata in metri) care le va multumi pe fete.
Din fericire, pentru unele teste, baietii au reusit sa cada la o invoiala cu juriul si va pot spune care vor fi subsecventele pentru cateva runde in avans.
Date de intrare
Pe prima linie a fisierului de intrare tango2.in se afla numerele N si C.
Pe a doua linie a fisierului se va afla sirul S, in care S[i] (indexat de la 1) = 'B' daca persoana cu numarul i este baiat si 'F' altfel.
Pe a treia linie a fisierului se afla Q, numarul de intervale interogate.
Pe urmatoarele Q linii se vor afla pe fiecare linie numerele X si Y. Pentru C = 1 capetele intervalului sunt chiar X si Y, iar pentru C = 2 capetele sunt X xor last si Y xor last unde last este raspunsul query-ului precedent (daca acesta este primul query atunci last = 0)
Date de ieşire
În fişierul de ieşire tango2.out se vor afla pe prima linie rezultatele intrebarilor separate prin spatii.
Restricţii
- Pentru alte 7 puncte: 1 ≤ N ≤ 2.000, 1 ≤ T ≤ 100.000 si C = 1
- Pentru 8 puncte: 1 ≤ N ≤ 250, 1 ≤ T ≤ 100.000 si C = 1
- Pentru alte 7 puncte: 1 ≤ N ≤ 100.000, 1 ≤ T ≤ 20 si C = 1
- Pentru alte 7 puncte: 1 ≤ N ≤ 100.000, 1 ≤ T ≤ 100.000 si C = 2
- Pentru alte 45 puncte: 1 ≤ N ≤ 100.000, 1 ≤ T ≤ 100.000 si C = 1
- Pentru alte 19 puncte: 1 ≤ N ≤ 1.000.000, 1 ≤ T ≤ 1.000.000 si C = 1
- Pentru alte 7 puncte: 1 ≤ N ≤ 1.000.000, 1 ≤ T ≤ 1.000.000 si C = 2
- Nota: Punctajele pe subtaskuri difera (foarte putin) fata de cele din concurs.
Exemplu
| tango2.in | tango2.out |
|---|---|
| 16 1 BFBFBBFFFBFBBFBF 6 1 2 5 10 6 15 8 12 8 13 1 16 | 1 5 9 0 7 10 |
Explicaţie
Acesta este un mod posibil de a realiza cea de-a treia runda de dans:
