Fişierul intrare/ieşire:ruine.in, ruine.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 ≤ qN).

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.inruine.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici