Fișierul intrare/ieșire ruine.in, ruine.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii