페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5649
서브태스크

아이템 획득 3초 1024MB

문제

여러분은 2차원 지도에서 자동차를 조종하여 아이템을 모으는 게임을 제작하고 있다.

 

지도에는 아이템을 얻을 수 있는 N개의 상자가 있다. i번째 상자의 위치는 (x_i​, y_i​)이고, 

자동차가 이 위치를 지나갈 때마다 w_i개의 아이템을 얻을 수 있다.

 

자동차는 x축 또는 y축에 평행한 방향으로 이동한다. 자동차의 이동은 두 정수 d와 v로 표현할 수 있다.

d=0이면 x좌표가 증가하는 방향으로 v만큼, d=1이면 y좌표가 증가하는 방향으로 v만큼,

d=2이면 x좌표가 감소하는 방향으로 v만큼, d=3이면 y좌표가 감소하는 방향으로 v만큼 이동한다.

 

이 때, 이동이 시작되는 위치에 있는 상자의 아이템은 얻을 수 없다. 

즉, (s_x, s_y)에서 (e_x, e_y)로 이동하는 경우, (s_x, s_y)에 있는 상자의 아이템은 얻을 수 없고, (e_x, e_y)에 있는 상자의 아이템은 얻을 수 있다.

 

자동차는 (1,1)에 시작해 총 Q번 이동한다. 자동차의 이동 방향과 거리가 주어지면, Q번 이동에서 얻게 되는 아이템의 총 개수를 구하시오.


입력

첫 번째 줄에 상자의 개수 N과 이동 횟수 Q가 공백으로 구분되어 주어진다.

이후 N개의 줄이 주어진다. 이 중 i번째 줄에는 세 정수 x_i, y_i, w_i가 공백으로 구분되어 주어진다. 이는 i 번째 상자가 (x_i, y_i)에 있으며, 이 위치를 지날 때마다 w_i개의 아이템을 얻게 됨을 의미한다.

이후 Q개의 줄이 주어진다. 이 중 j번째 줄에는 두 정수 d_j , v_j가 공백으로 구분되어 주어진다. 이는 자동 차가 d_j방향으로 v_j만큼 이동함을 의미한다.

[제약 조건]

  • 1 \leq N \leq 200,000

  • 1 \leq Q \leq 200,000

  • 1 \leq x_i \leq 200,000

  • 1 \leq y_i \leq 200,000

  • 1 \leq w_i \leq 200,000

  • 0 \leq d_j \leq 3

  • 1 \leq v_j \leq 200,000

  • 상자의 위치는 서로 다르다.

  • 매 순간 자동차의 x,y좌표는 1 이상 200,000 이하이다.

  • 주어지는 모든 수는 모두 정수이다.


출력

첫 번째 줄에 Q번의 이동에서 얻게 되는 아이템의 총 개수를 출력한다.


부분문제

번호 점수 조건
#19점

N \leq 2,000 , Q \leq 2000, x_i \leq 1,000, y_i \leq 1,000, w_i \leq 10, 매 순간 자동차의 x,y좌표는 1,000 이하이다.

#217점

N=2,000, Q \leq 2,000, w_i \leq 10

#315점

모든 상자의 x좌표가 서로 다르고, y좌표가 서로 다르다.

#437점

w_1 = 1

#522점

추가 제약 조건 없음.


예제1

입력
46

553

585

352

151

04

19

35

23

21

05
출력
24

이동할 때마다 초록색으로 표시된 아이템을 얻는다.


예제2

입력
33

131

221

311

13

02

33
출력
2

출처

KOI 2023 1차 초 3번

역링크