시간 제한메모리 제한제출정답맞은 사람정답 비율
7 초 (추가 시간 없음) 1024 MB3510834.783%

문제

선린국은 천하제일국과 2차원 좌표평면으로 나타나는 전장에서 전쟁을 하고 있다. 미사일 기술이 발달된 선린국은 미사일 폭격을 통해 천하제일국과의 전쟁에서 승리를 거두려고 한다.

선린국의 군대는 천하제일국에 비밀요원 김준겸을 심어놓았다. 비밀요원 김준겸은 암호화된 적군의 이동 계획을 해독하여 당신에게 전달했다. 김준겸은 프로페셔널하기 때문에, 계획과 다르게 부대가 움직이는 경우는 없다.

천하제일국의 군대는 $N$개의 부대로 구성되어 있다. 당신이 전달받은 계획에 따르면, 각 부대는 전장의 특정 지점에 정확히 한 번 출몰한 뒤, 만약 섬멸되지 않았다면 시간이 흐른 후 본부로 복귀할 예정이다.

당신은 천하제일국 부대가 몸 성히 돌아가는 것을 원치 않기 때문에 미사일 폭격을 수행할 계획을 짜 두었다. 미사일을 맞은 부대는 완전히 섬멸되어 없어진다. 당신은 미사일 폭격 계획과 비밀요원 김준겸이 보내오는 적군의 이동 계획이 합쳐진 리스트를 보고 순서대로 사건이 일어났을 때 얼마나 많은 부대를 섬멸할 수 있을지 계산해야 한다.

 

구체적으로, 다음과 같은 3가지 정보로 구성된 리스트가 주어진다. 리스트의 계획은 주어진 순서대로 수행된다.

  • 1 $x$ $y$ $r$ : 선린국은 $(x, y)$를 중심으로 $(x$ 좌표의 차이$) + (y$ 좌표의 차이$) \leq r$인 구역을 미사일로 공격할 것이다.
  • 2 $x$ $y$ : 해독된 계획표에 따르면, $(x, y)$ 지점에 천하제일국의 부대가 출몰한다.
  • 3 $i$ : 해독된 계획표에 따르면, $i$번째로 출몰한 천하제일국의 부대가 본부로 돌아간다.

요원이 보내온 정보와 선린국의 미사일 폭격 정보가 주어질 때, 천하제일국의 군대를 몇 부대 섬멸할 수 있는지 구하는 프로그램을 작성하라.

입력

첫째 줄에 3개의 자연수 $N, M, K$가 공백으로 주어진다.

둘째 줄부터 $M+K$개의 줄에 1, 2, 3번 정보 중 하나가 한 줄에 하나씩 주어진다. 1번 쿼리는 정확히 $M$번 주어지고, 2번 쿼리와 3번 쿼리는 합쳐서 총 $K$번 주어진다.

출력

천하제일국의 군대를 몇 부대 섬멸할 수 있는지 출력한다.

제한

  • $1 \leq N, M, K \leq 200\,000$
  • $K \leq 2N$
  • $1 \leq x, y, r \leq 500$
  • $i$는 해당 시점까지 주어진 2번 쿼리의 개수 이하이다.
  • 2번 쿼리는 최대 $N$번 주어진다.
  • 2번 쿼리로 주어지는 좌표는 모두 다르다.
  • 적군의 각 부대는 최대 한 번 출몰하고, 최대 한 번 본부로 돌아가고, 본부로 돌아간 부대는 다시 나타나지 않는다.

예제 입력 1

3 5 5
1 3 5 2
2 2 2
1 3 3 2
1 3 3 2
3 1
2 3 3
1 5 5 1
3 2
2 4 4
1 1 1 8

예제 출력 1

2

$(2, 2)$에 위치한 1번 부대는 $(3, 3)$에 떨어진 크기 $2$짜리 폭격에 의해 섬멸당한다.

$(4, 4)$에 위치한 3번 부대는 $(1, 1)$에 떨어진 크기 $8$짜리 폭격에 의해 섬멸당한다.

출처

High School > 선린인터넷고등학교 > 2021 선린 정보 알고리즘경시대회 E번