题目详情题解（0）讨论（0）提交记录（0）

AT_abc385_d.[ABC385D] Santa Claus 2

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二次元平面上有 NN 个点 (X1,Y1),…,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N) 建有房子。

最初，圣诞老人在点 (Sx,Sy)(S_x,S_y)。圣诞老人将按照序列 (D1,C1),…,(DM,CM)(D_1,C_1),\ldots,(D_M,C_M) 进行以下行动：

  • 对于 i=1,2,…,Mi=1,2,\ldots,M，按顺序进行以下移动：
    • 设 (x,y)(x,y) 为他当前所在的点。
      • 如果 DiD_i 是 U，则从 (x,y)(x,y) 沿直线移动到 (x,y+Ci)(x,y+C_i)。
      • 如果 DiD_i 是 D，则从 (x,y)(x,y) 沿直线移动到 (x,y−Ci)(x,y-C_i)。
      • 如果 DiD_i 是 L，则从 (x,y)(x,y) 沿直线移动到 (x−Ci,y)(x-C_i,y)。
      • 如果 DiD_i 是 R，则从 (x,y)(x,y) 沿直线移动到 (x+Ci,y)(x+C_i,y)。

请找出他完成所有行动后所在的点，以及他在行动过程中经过或到达的不同房子的数量。如果多次经过同一个房子，只计数一次。

输入格式

输入从标准输入按以下格式给出：

NN MM SxS_x SyS_y
X1X_1 Y1Y_1
…\dots
XNX_N YNY_N
D1D_1 C1C_1
…\dots
DMD_M CMC_M

输出格式

设 (X,Y)(X,Y) 为他完成所有行动后所在的点，CC 为他在行动过程中经过或到达的不同房子的数量。按顺序输出用空格分隔的 XX、YY、CC。

输入输出样例

  • 输入#1

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

    输出#1

    2 3 2

  • 输入#2

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

    输出#2

    3000000000 0 0

说明/提示

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • 1≤M≤2×1051 \leq M \leq 2\times 10^5
  • −109≤Xi,Yi≤109-10^9 \leq X_i,Y_i \leq 10^9
  • (Xi,Yi)(X_i,Y_i) 互不相同
  • −109≤Sx,Sy≤109-10^9 \leq S_x,S_y \leq 10^9
  • 点 (Sx,Sy)(S_x,S_y) 没有房子
  • 每个 DiD_i 是 U、D、L、R 之一
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • 所有给定数字均为整数

【样例 #1 解释】

圣诞老人的行动如下图所示：

  • D1=D_1= L，所以他从 (3,2)(3,2) 直线移动到 (3−2,2)(3-2,2)。在此期间，他经过 (2,2)(2,2) 处的房子。
  • D2=D_2= D，所以他从 (1,2)(1,2) 直线移动到 (1,2−1)(1,2-1)。
  • D3=D_3= R，所以他从 (1,1)(1,1) 直线移动到 (1+1,1)(1+1,1)。在此期间，他经过 (2,1)(2,1) 处的房子。
  • D4=D_4= U，所以他从 (2,1)(2,1) 直线移动到 (2,1+2)(2,1+2)。在此期间，他经过 (2,2)(2,2) 处的房子，但该房子已经被经过。

他在行动期间经过或到达的房子数量为 22。

【样例 #2 解释】

小心溢出。

输入解题思路，AI测评打分。不知道怎么写?

首页