← 返回题目列表

AtCoder · abc385_d

G. 圣诞老人 2

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

有 N 各点的房屋 (X_1,Y_1),\ldots,(X_N,Y_N) 在二维平面上。

最初,圣诞老人就在现场 (S_x,S_y)。他会按照顺序行动 (D_1,C_1),\ldots,(D_M,C_M) 如下:

  • 对于 i=1,2,\ldots,M 按顺序,他的动作如下:
    • 让 (x,y) 是他当前所在的点。
      • If D_i is U,从 (x,y) to (x,y+C_i).
      • If D_i is D,从 (x,y) to (x,y-C_i).
      • If D_i is L,从 (x,y) to (x-C_i,y).
      • If D_i is R,从 (x,y) to (x+C_i,y).

找出他完成所有动作后所在的点,以及他在动作过程中经过或到达的不同房屋的数量。如果同一栋房子经过多次,只算一次。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i \leq 10^9
  • 对 (X_i,Y_i) 是不同的。
  • -10^9 \leq S_x,S_y \leq 10^9
  • 没有房子 (S_x,S_y).
  • 每个 D_i 是其中之一 U, D, L, R.
  • 1 \leq C_i \leq 10^9
  • 所有输入数字均为整数。

输入

输入由标准输入按以下格式给出:

N M S_x S_y
X_1 Y_1
\vdots
X_N Y_N
D_1 C_1
\vdots
D_M C_M

输出

让 (X,Y) 是他完成所有动作后所在的点,并且 C 是经过或到达的不同房屋的数量。打印 X,Y,C 按此顺序用空格分隔。


示例输入 1

3 4 3 2
2 2
3 3
2 1
L 2
D 1
R 1
U 2

示例输出 1

2 3 2

圣诞老人的行为如下:

Figure

  • D_1= L,所以他从 (3,2) to (3-2,2) 呈直线。在此期间,他经过房子 (2,2).
  • D_2= D,所以他从 (1,2) to (1,2-1) 呈直线。
  • D_3= R,所以他从 (1,1) to (1+1,1) 呈直线。在此期间,他经过房子 (2,1).
  • D_4= U,所以他从 (2,1) to (2,1+2) 呈直线。在此期间,他经过房子 (2,2),但已经通过了。

他的行动中经过或到达的房屋数量为 2.


示例输入 2

1 3 0 0
1 1
R 1000000000
R 1000000000
R 1000000000

示例输出 2

3000000000 0 0

小心溢出。