페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

입력
4 6

5 5 3

5 8 5

3 5 2

1 5 1

0 4

1 9

3 5

2 3

2 1

0 5
출력
24

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


예제2

입력
3 3

1 3 1

2 2 1

3 1 1

1 3

0 2

3 3
출력
2

출처

KOI 2023 1차 초 3번

역링크 공식 문제집만