9014: Italian Brainrot
[만든사람 : jbs34_KHJ]
문제 설명
어느 해양 스타디움에서 트랄랄레로 트랄랄라들이 데스 매치를 벌이고 있다.
스타디움은 2차원 격자로 표현된다.
- 각 칸에는 트랄랄레로 트랄랄라 하나 또는 빈 칸이 있다.
- 1~N 각 트랄랄레로 트랄랄라는 힘이 다르며, 각각 고유의 번호(1~N)와 공격력 $S$를 가진다.
- 트랄랄레로 트랄랄라들은 L→R 방향으로 물기 공격을 하는데 한 번의 공격은 다음 규칙에 따라 진행된다.
트랄랄레로 트랄랄라 $T_i$는 번호 순서(1, 2, … , N)대로 공격한다.
공격 시 $T_i$는 자신의 공격력 $S_i$만큼 오른쪽으로 직선 공격을 한다.
- $T_i$가 위치한 칸을 $(r,\; c)$라고 할 때,
- 공격 범위는 $(r,\; c+1)$부터 $(r,\; c+S_i)$이다.
- 범위 내에서 가장 먼저 발견되는 트랄랄레로 트랄랄라 $T_j$ 1마리만 타격한다.
타격된 $T_j$는 다음을 겪는다:
1. 공격 받은 $T_j$의 공격력은 2로 나눈 몫이 된다.
2. 공격력 감소 후 0이 되면 즉시 탈락(격자에서 사라짐)한다.
각 트랄랄레로 트랄랄라는 자신의 공격 턴이 오기 전에 탈락하면 공격하지 못한다.
모든 트랄랄레로 트랄랄라가 한 번씩 공격한 뒤, 생존한 트랄랄레로 트랄랄라 수를 출력하시오.
스타디움은 2차원 격자로 표현된다.
- 각 칸에는 트랄랄레로 트랄랄라 하나 또는 빈 칸이 있다.
- 1~N 각 트랄랄레로 트랄랄라는 힘이 다르며, 각각 고유의 번호(1~N)와 공격력 $S$를 가진다.
- 트랄랄레로 트랄랄라들은 L→R 방향으로 물기 공격을 하는데 한 번의 공격은 다음 규칙에 따라 진행된다.
트랄랄레로 트랄랄라 $T_i$는 번호 순서(1, 2, … , N)대로 공격한다.
공격 시 $T_i$는 자신의 공격력 $S_i$만큼 오른쪽으로 직선 공격을 한다.
- $T_i$가 위치한 칸을 $(r,\; c)$라고 할 때,
- 공격 범위는 $(r,\; c+1)$부터 $(r,\; c+S_i)$이다.
- 범위 내에서 가장 먼저 발견되는 트랄랄레로 트랄랄라 $T_j$ 1마리만 타격한다.
타격된 $T_j$는 다음을 겪는다:
1. 공격 받은 $T_j$의 공격력은 2로 나눈 몫이 된다.
2. 공격력 감소 후 0이 되면 즉시 탈락(격자에서 사라짐)한다.
각 트랄랄레로 트랄랄라는 자신의 공격 턴이 오기 전에 탈락하면 공격하지 못한다.
모든 트랄랄레로 트랄랄라가 한 번씩 공격한 뒤, 생존한 트랄랄레로 트랄랄라 수를 출력하시오.
입력 설명
첫 줄엔 스타디움의 크기 $R,\;C$와 트랄랄레로 트랄랄라의 수 $N$이 주어진다.
$(1 ≤ R, C ≤ 200\;000,\ R×C ≤ 200\;000)$
$(1 ≤ N ≤ 200\;000)$
다음 $N$ 줄 동안엔 트랄랄레로 트랄랄라의 번호 $i$와 트랄랄레로 트랄랄라의 위치 $(r, \;c)$,
그리고 $i$번 트랄랄레로 트랄랄라의 공격력 $S$가 주어진다.
$(1 ≤ i ≤ N)$
$(1 ≤ S ≤ 10^9)$
$(1 ≤ R, C ≤ 200\;000,\ R×C ≤ 200\;000)$
$(1 ≤ N ≤ 200\;000)$
다음 $N$ 줄 동안엔 트랄랄레로 트랄랄라의 번호 $i$와 트랄랄레로 트랄랄라의 위치 $(r, \;c)$,
그리고 $i$번 트랄랄레로 트랄랄라의 공격력 $S$가 주어진다.
$(1 ≤ i ≤ N)$
$(1 ≤ S ≤ 10^9)$
출력 설명
한 턴씩 모든 트랄랄레로 트랄랄라의 공격이 끝난 뒤 격자에 남아 있는 트랄랄레로 트랄랄라의 수를 출력하시오.
입력 예시 Copy
3 10 3
1 1 2 5
2 1 6 3
3 1 8 4
출력 예시 Copy
3
도움
빈칸을 x라고 하면 배치는
xx1xxx2x3x
…(생략)가 된다.
1번 트랄랄레로 트랄랄라(공격력 5)는 오른쪽으로 5칸 공격해 2번 트랄랄레로 트랄랄라가 먼저 맞는다.
이에 따라 트랄랄레로 트랄랄라 2의 공격력은 3에서 1로 감소한다.
2번 트랄랄레로 트랄랄라(공격력 1)는 공격해도 범위 내 타격이 없다.
3번 트랄랄레로 트랄랄라는 공격력 4이고 범위 내 타격이 없으므로 남은 트랄랄레로 트랄랄라는 3마리다.
xx1xxx2x3x
…(생략)가 된다.
1번 트랄랄레로 트랄랄라(공격력 5)는 오른쪽으로 5칸 공격해 2번 트랄랄레로 트랄랄라가 먼저 맞는다.
이에 따라 트랄랄레로 트랄랄라 2의 공격력은 3에서 1로 감소한다.
2번 트랄랄레로 트랄랄라(공격력 1)는 공격해도 범위 내 타격이 없다.
3번 트랄랄레로 트랄랄라는 공격력 4이고 범위 내 타격이 없으므로 남은 트랄랄레로 트랄랄라는 3마리다.