Fişierul intrare/ieşire:tango2.in, tango2.outSursăLot Deva Seniori 2019, baraj 2
AutorAndrei ConstantinescuAdăugată deAlexandruLuchianov1Alex Luchianov AlexandruLuchianov1
Timp execuţie pe test1.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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: 1N2.000, 1T100.000 si C = 1
  • Pentru 8 puncte: 1N250, 1T100.000 si C = 1
  • Pentru alte 7 puncte: 1N100.000, 1T20 si C = 1
  • Pentru alte 7 puncte: 1N100.000, 1T100.000 si C = 2
  • Pentru alte 45 puncte: 1N100.000, 1T100.000 si C = 1
  • Pentru alte 19 puncte: 1N1.000.000, 1T1.000.000 si C = 1
  • Pentru alte 7 puncte: 1N1.000.000, 1T1.000.000 si C = 2
  • Nota: Punctajele pe subtaskuri difera (foarte putin) fata de cele din concurs.

Exemplu

tango2.intango2.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:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?