시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 5 | 4 | 4 | 80.000% |
Na jednom programerskom natjecanju sudjeluje n natjecatelja. Prije natjecanja svaki je natjecatelj od gospodina Malnara dobio majicu. Neki su natjecatelji dobili žute, a neki crne majice, čime je nastalo rivalstvo između crnog i žutog tima.
Na početku natjecanja svi natjecatelji imaju 0 bodova te je za svakoga poznata boja njegove majice. Tijekom natjecanja dogodilo se q promjena u rezultatima. U i-toj promjeni je natjecatelj xi upravo dobio još di bodova.
Svaki natjecatelj u žutoj majici računa svoju kaznu (tzv. crni ceh) kao broj natjecatelja u crnoj majici koji u tom trenutku imaju strogo više bodova od njega. Izračunajte i ispišite koliki je zbroj kazni natjecatelja u žutim majicama nakon svake promjene u bodovima.
U prvom su retku prirodni brojevi n (1 ≤ n ≤ 105) i q (1 ≤ q ≤ 3 · 105) iz teksta zadatka.
U sljedećem je retku riječ od n znakova koja opisuje boju majice svakog natjecatelja. Svaki znak u toj riječi je jedno od velikih slova C ili Z koje označava boju majice i-tog natjecatelja (crna ili žuta). Postojat će barem jedan natjecatelj sa crnom i barem jedan natjecatelj sa žutom majicom.
U sljedećih se q redaka nalaze po dva prirodna broja xi (1 ≤ xi ≤ n) i di (1 ≤ di ≤ 3 · 105).
Maksimalan broj bodova koje neki natjecatelj može osvojti na natjecanju je 3 · 105.
U i-ti od q redaka izlaza, ispišite ukupan crni ceh nakon i-te promjene.
3 3 CZZ 1 10 2 20 3 5
2 1 1
4 6 CZCZ 3 70 3 30 2 100 1 10 4 80 1 100
2 2 1 2 1 3