#P12656. [KOI 2023 Round 1] 道具获取

[KOI 2023 Round 1] 道具获取

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

你正在开发一款游戏,玩家将在二维地图中驾驶汽车收集道具。

地图上有 NN 个可以获取道具的箱子。第 ii 个箱子的位置是 (xi,yi)(x_i, y_i),每当汽车经过这个位置时,可以获得 wiw_i 个道具。

汽车只能沿与 x 轴或 y 轴平行的方向移动。汽车的每次移动通过两个整数 ddvv 来表示:

  • d=0d = 0,表示 x 坐标增加 vv
  • d=1d = 1,表示 y 坐标增加 vv
  • d=2d = 2,表示 x 坐标减少 vv
  • d=3d = 3,表示 y 坐标减少 vv

此时,位于起点位置的箱子不能获取道具。换句话说,如果汽车从 (sx,sy)(s_x, s_y) 移动到 (ex,ey)(e_x, e_y),则不能获取 (sx,sy)(s_x, s_y) 位置的箱子的道具,但可以获取 (ex,ey)(e_x, e_y) 位置的箱子的道具。

汽车从 (1,1)(1, 1) 开始,接下来会移动 QQ 次。给出汽车的移动方向和距离,计算 QQ 次移动过程中能够获得的道具总数。

输入格式

第一行包含两个用空格分隔的整数 NNQQ,分别表示箱子的数量和汽车的移动次数。

接下来的 NN 行中,每行包含三个整数 xix_iyiy_iwiw_i,表示第 ii 个箱子的位置在 (xi,yi)(x_i, y_i),且经过该位置可以获得 wiw_i 个道具。

接下来的 QQ 行中,每行包含两个整数 djd_jvjv_j,表示汽车向方向 djd_j 移动距离 vjv_j

输出格式

输出一行,表示 QQ 次移动过程中能获得的道具总数。

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
3 3
1 3 1
2 2 1
3 1 1
1 3
0 2
3 3
2

提示

样例 1 说明

如图所示,每次移动都会获得绿色标记的物品。

限制条件

  • 所有输入数值均为整数。
  • 1N2000001 \leq N \leq 200\,000
  • 1Q2000001 \leq Q \leq 200\,000
  • 1xi2000001 \leq x_i \leq 200\,000
  • 1yi2000001 \leq y_i \leq 200\,000
  • 1wi2000001 \leq w_i \leq 200\,000
  • 0dj30 \leq d_j \leq 3
  • 1vj2000001 \leq v_j \leq 200\,000
  • 所有箱子的位置彼此不同。
  • 汽车在任意时刻的 x、y 坐标都在 [1,200000][1, 200\,000] 范围内。

子问题

  1. (9 分)N2000N \leq 2\,000Q2000Q \leq 2\,000xi1000x_i \leq 1\,000yi1000y_i \leq 1\,000wi10w_i \leq 10,汽车所有时刻的坐标 1000\leq 1\,000
  2. (17 分)N2000N \leq 2\,000Q2000Q \leq 2\,000wi10w_i \leq 10
  3. (15 分)所有箱子的 x 坐标互不相同,且 y 坐标也互不相同。
  4. (37 分)所有 wi=1w_i = 1
  5. (22 分)无额外限制。

翻译由 ChatGPT-4o 完成