Fişierul intrare/ieşire:election.in, election.outSursăBOI 2018
AutorAndrei Constantinescu, Bogdan CiobanuAdăugată deAndrei1998Andrei Constantinescu •Andrei1998
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Election

Astăzi trebuie să decidem care este cea mai bună echipă de supereroi: Echipa Căpitanului sau Echipa Iron Man (Tony)?
Sunt N fani nervoşi, iar fiecare dintre ei trebuie să voteze pentru echipa lui preferată de supereroi: fie C (Căpitanul), sau T (Tony).
Cum Căpitanul ştie că nu are nicio şansă de câştig, şi cum este un om cinstit, decide să fraudeze alegerile. El vrea să anuleze un număr minim de voturi.
Votarea se face de două ori separat:

  • în ordinea crescătoare a indicilor fanilor (mai puţin cei cu votul anulat).
  • în ordinea descrescătoare a indicilor fanilor (mai puţin cei cu votul anulat).

Căpitanul este fericit dacă la fiecare moment în timpul numărării voturilor el NU pierde lui Tony (nu are nevoie să aibă mai multe voturi, ci doar să nu aibă strict mai puţine).
Desigur, nimeni nu se poate lua de Tony. El ştie planul Căpitanului, şi ar vrea să ştie pentru Q scenarii care este numărul de voturi pe care Căpitanul le va anula. Un scenariu este definit de două numere L şi R, ce semnfică că doar fanii cu indicii de la L la R inclusiv au să participe la sesiunea de votare

Date de intrare

Prima linie a fişierului de intrare election.in conţine un singur număr N, numărul de fani.
A doua linie conţine un şir de N caractere din mulţimea {C, T}, voturile fiecărui fan.
A treia linie conţine un singur număr Q, numărul de scenarii.
Următoarele Q linii descriu cele Q scenarii în forma L R, unde 1 ≤ L ≤ R ≤ N.

Date de ieşire

Fişierul de ieşire election.out conţine Q linii. A i-a linie va conţine rezultatul pentru cel de-al i-leq scenariu.

Restricţii și precizări

  • Pentru 28 puncte, 1 ≤ N, Q ≤ 2.000
  • Pentru alte 54 puncte, 1 ≤ N, Q ≤ 70.000
  • Pentru alte 18 puncte, 1 ≤ N, Q ≤ 500.000

Exemple

election.inelection.out
11
CCCTTTTTTCC
3
1 11
4 9
1 6
4
6
3

Explicatie

În primul scenariu, voturile arată aşa: CCCTTTTTTCC. Singura soluţie e să se anuleze 4 dintre voturile pentru Tony.
În cel de al doilea scenariu, voturile arată aşa: TTTTTT. Singura soluţie e să se anuleze toate voturile.
În ultimul scenariu, voturile arată aşa: CCCTTT. Singura soluţie e să se anuleze toate voturile lui Tony.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?