分数: 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).
- If D_i is
- 让 (x,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
圣诞老人的行为如下:

- 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
小心溢出。