Fișierul intrare/ieșire | ruine.in, ruine.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Ruine
Într-o regiune turistică sunt N sate dispuse în linie. Inițial, oricare două sate vecine sunt unite printr-un drum. Cu timpul, drumurile se surpă și nimeni nu le repară. În fiecare sat i sunt Ti obiective turistice de vizitat. Biroul de Turism din regiune primește mesaje de două tipuri:
- primăriile anunță când un drum se surpă
- turiștii pun întrebări de forma: „Câte obiective pot fi vizitate în satul q și în satele la care se mai poate ajunge din q ”?
Date de intrare
Fișierul de intrare ruine.in conține pe prima linie numerele N și M, reprezentând numărul de sate și numărul de mesaje primite de Biroul de Turism. Pe a doua linie se află N numere T1, T2, ..., TN. Pe următoarele M linii sunt mesajele primite de Biroul de Turism, sub formele:
- S q — mesajul indică că drumul între satele q și q + 1 s-a surpat (1 ≤ q < N);
- T q — mesajul întreabă numărul total de obiective în satul q și în satele accesibile din q (1 ≤ q ≤ N).
Date de ieșire
În fișierul de ieșire ruine.out se vor tipări răspunsurile la interogările de tip „T”, câte unul pe linie, în ordinea în care au fost puse întrebările.
Restricții
- 1 ≤ N ≤ 100.000;
- 1 ≤ M ≤ 200.000;
- 1 ≤ Ti ≤ 1.000;
Exemplu
ruine.in | ruine.out |
---|---|
6 7 2 8 5 4 3 4 T 4 S 2 T 4 T 1 S 5 T 2 T 6 |
26 16 10 10 4 |
Explicație
Inițial, din satul 4 se poate ajunge în toate satele.
Se surpă drumul 2-3.
Din satul 4 se poate ajunge în satele 3, 5 și 6.
Din satul 1 se poate ajunge în satul 2.
Se surpă drumul 5-6.
Din satul 2 se poate ajunge în satul 1.
Satul 6 este izolat.