ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#5693

공 이동 시뮬레이션 1s 128MB

問題

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

  • 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))

  • 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))

  • 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))

  • 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

제한사항

  • 1 ≤ n ≤ 109

  • 1 ≤ m ≤ 109

  • 0 ≤ x < n

  • 0 ≤ y < m

  • 1 ≤ q(=쿼리의 수) ≤ 200,000


入力

첫 번째 줄에 격자의 행의 개수 n, 열의 개수 m, 정수 x와 y가, 쿼리의 수 q가 주어집니다.

다음 줄 부터 q개의 줄에 쿼리의 방향과 dx가 주어집니다.


出力

n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 q개의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 출력해주세요.


部分問題

番号 点数 条件
#15点

하나의 쿼리만 주어집니다.

#295点

추가적인 조건이 없습니다.


例題 #1

2 2 0 0 5
2 1
0 1
1 1
0 1
2 1
4

例題 #2

2 5 0 1 6
3 1
2 2
1 1
2 3
0 1
2 1
2

出典

월간 코드 챌린지 시즌3
ログインしないとコードを書けません。