Submit solution
Points:
2000 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Có n ô vuông được đánh số từ 1 đến n từ trái sang phải. Ô vuông thứ i được đánh dấu bởi kí tự s_{i}. Ban đầu tất cả các ô vuông mỗi ô vuông đều có một con robot.
q lần.
có thể đẩy các con robot ấyLần đẩy thứ i sẽ có hai kí tự lần lượt là t_{i} và d_{i}, trong đó d_{i} là L
hoặc R
. Khi đẩy robot, tất cả các con robot có đứng ở ô vuông có kí tự t_{i} sẽ bị đẩy sang trái nếu d_{i} là L
, sẽ bị đẩy sang phải nếu d_{i} là R
.
Tuy nhiên khi 1 sang trái hoặc đẩy các con robot đang đứng ở ô vuông thứ n sang phải thì các con robot đó đột nhiên biến mất.
đẩy các con robot đang đứng ở ô vuông thứYêu Cầu: Bạn hãy đếm số con robot chưa bị biến mất sau khi q lần.
đẩy các con robot ấyInput
- Dòng đầu tiên chứa hai số nguyên dương n và q (1 \leq n, q \leq 2 \times 10^{5}).
- Dòng tiếp theo chứa chuỗi s (độ dài của xâu không quá n và chỉ chứa chữ cái tiếng Anh in hoa).
- Dòng tiếp theo chứa hai giá trị là t_{i} và d_{i} (1 \leq i \leq q), mỗi bộ đôi giá trị cách nhau một dòng.
- t_{i} chỉ chứa chữ cái tiếng Anh in hoa và d_{i} chỉ tồn tại hai giá trị là
L
hoặcR
.
Output
- In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.
Scoring
- Subtask 1 (50\% số điểm): Có n, q \leq 100.
- Subtask 2 (50\% số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
3 4
ABC
A L
B L
B R
A R
Output
2
Note
- Ban đầu tất cả các con robot hiện còn đang ở mỗi ô vuông.
- Lần đẩy đầu tiên, con đứng ở ô vuông đầu tiên bị biến mất.
- Lần đẩy thứ hai, con đứng ở ô vuông thứ hai bị đẩy sang bên trái và đứng ở ô vuông đầu tiên.
- Lần đẩy thứ ba, không con nào bị đẩy.
- Lần đẩy cuối cùng, con đứng ở ô vuông đầu tiên bị đẩy sang bên phải.
Như vậy còn 2 con chưa bị biến mất.
Comments
tại s test bày lại ra 3 vậy
10 15
SNCZWRCEWB
B R
R R
E R
W R
Z L
S R
Q L
W L
B R
C L
A L
N L
E R
Z L
S L