루미 알고리즘

#1639플래티넘Tina Scoreboard

PO 2026 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

ICPC is a programming competition where you have five hours to solve as many problems as possible. This problem is about a competition that is similar, but not exactly the same as the official ICPC.

In this competition, teams make submissions on problems. For each submission, you do not receive points: you only get Accepted or Wrong Answer.

At the end of the contest, a ranking of the teams is established in the following way. First, we count how many problems each team has solved; let this be denoted by an integer p. Then we compute each team's submission penalty. For each problem that a team gets Accepted on, the submission penalty is equal to the number of incorrect submissions the team made on that problem. The total submission penalty for a team is the sum of the submission penalties over all problems that they solved, which we denote by an integer t. Each team's result can therefore be described by the ordered pair (p, t). Note that if a team never solves a certain problem during the entire contest, then they receive no submission penalty from that problem.

The rank of a given team is the number of teams that are strictly better. A team i is strictly better than another team j if either

(p_i > p_j) or (p_i = p_j and t_i < t_j)

holds.

The table below shows an example of the ranks that different teams receive, given a set of p and t values.

Rankpt
010500
191000
28500
37300
37300
57376
66250

Note that if two teams have exactly the same result, they receive the same rank.

During the first four hours of the contest, each team can see whether their submissions were Accepted. They can also see the results of other teams' submissions via the scoreboard.

During the last hour, the scoreboard is frozen, and thus teams can only see the results of their own submissions. Each team can still see when new submissions are made by other teams, but not their results.

When the contest is over, it is time to unfreeze the scoreboard. This is done by revealing the result of each submission one at a time. Depending on the order in which this is done, it can be more or less exciting for the teams. This is because the rank of a team is primarily determined by how many problems they have solved. For example, if a certain team has solved 4 problems and it is revealed that all other teams have solved more, then that team loses interest. If the submissions had instead been revealed in an order such that it takes longer for them to find this out, it would of course be more exciting.

Tina aims to make ICPC more exciting. She has therefore proposed an order in which the results of submissions should be revealed. Given this order, she wants to compute for each team the number of submissions that are revealed before they lose interest.

More precisely, assume that after each revealed submission, every team considers all possible outcomes of finishing the unfreezing of the scoreboard. If a given team has the same final position in all these outcomes, then that team loses interest. Tina then wants to know, for each team, the number of submissions that were revealed before they lost interest.

For the order to be reasonable, she guarantees that each team's submissions on a given problem are ordered by time, so that earlier submissions come first.

Input

The first line contains four integers N, P, H, and F (1 ≤ N ≤ 2 · 10^5, 1 ≤ P ≤ 15, 0 ≤ H ≤ 2 · 10^5, 1 ≤ F ≤ 2 · 10^5), the number of teams, the number of problems, the number of submissions before the freeze, and the number of submissions during the freeze.

The following H lines describe the submissions that occurred before the freeze. Each such submission is described by the integers w and p and the string r (1 ≤ w ≤ N, 1 ≤ p ≤ P, r ∈ {AC, WA}), meaning that the team with index w submitted to problem p, and the result was r. If r is AC, the submission was Accepted; otherwise it was not. These submissions are given in chronological order.

The following F lines describe the submissions that occurred during the freeze. Their format is identical to the submissions that occurred before the freeze. They are given in the order that Tina is curious about. It is guaranteed that for each team, submissions to a given problem appear in chronological order. No other guarantees are given.

Note: it is also guaranteed that a team will never submit to a problem that they have already solved, either before or during the freeze.

Output

For each team, output the number of submissions that were revealed before the team lost interest. Print these values space-separated on a single line. Note that if a team knows its final position before the unfreezing begins, you should output 0 for that team.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
15N ≤ 50, P = 1, and each team makes at most one submission per problem.
26N ≤ 50, and each team makes at most one submission per problem.
315N, F, H ≤ 50
48N, F, H ≤ 500
530N, F, H ≤ 2000
636No additional constraints.

Explanation of Samples

Sample case 1: before the scoreboard is frozen, team 2 already knows that they will finish with 1 solved problem and 0 submission penalty. Thus, they already know their final rank. Team 1 does not know whether team 2 will solve the problem or not, but even if the other team solves the problem, their result cannot worsen the rank of team 1.

Sample case 2: similarly to sample case 1, team 2 already has all the information. Team 1, however, cannot be certain of its final position immediately after the contest, since if team 2 solves the problem, team 1 loses one rank. When the result is finally revealed, they become certain.

Sample case 3: even though it may not seem so, team 1 can immediately figure out that they have won the contest. Since a team never submits to a problem they have already solved, team 1 knows that the only submission from team 2 that could be Accepted is the last one. Even if that submission is Accepted, it will not affect their rank.

예제

예제 1

입력
2 1 1 1
1 1 AC
2 1 AC
출력
0 0 

예제 2

입력
2 1 2 1
1 1 WA
1 1 AC
2 1 AC
출력
1 0 

예제 3

입력
2 1 2 3
1 1 WA
1 1 AC
2 1 WA
2 1 WA
2 1 AC
출력
0 0 

예제 4

입력
2 1 3 1
1 1 WA
1 1 AC
2 1 WA
2 1 AC
출력
0 0 

예제 5

입력
2 2 3 2
1 1 WA
1 1 AC
1 2 AC
2 1 WA
2 2 AC
출력
1 0 

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.