AT_tkppc2016_e.歩くNPCたち（Walking NPCs）

通过率：0%

AC君温馨提醒

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

题目描述

joisino姐姐的下一个工作是检查游戏中 NPC 的移动情况。
在一条无限延伸的直线上，站着 $N$ 个 NPC。
他们每个人都以一定的速度朝着固定的方向行走。
以直线上的某一点为基准，从该点向右移动 $x$ 的位置用坐标 $x$ 表示。
游戏开始时，第 $i$ 个 NPC 站在坐标 $X_i$ ，并且每秒移动 $V_i$ 的距离。
更准确地说，游戏开始 $t$ 秒后，第 $i$ 个 NPC 会在坐标 $X_i + V_i \times t$ 的位置。
可能有两个或更多 NPC 在同一时刻处于同一位置。
为了确认这些 NPC 的移动是否符合游戏的设定，需要回答 $Q$ 个问题。
第 $i$ 个问题是：在游戏开始 $T_i$ 秒后，坐标 $L_i$ 到 $R_i$ 之间有多少个 NPC？
如果 NPC 恰好在 $L_i$ 或 $R_i$ 的位置，也算作在 $L_i$ 到 $R_i$ 之间。
joisino姐姐的任务是编写程序，回答所有这些问题。

输入格式

输入以如下格式从标准输入读入。

$N$
$X_1$ $V_1$
$X_2$ $V_2$
$\vdots$
$X_N$ $V_N$
$Q$
$T_1$ $L_1$ $R_1$
$T_2$ $L_2$ $R_2$
$\vdots$
$T_Q$ $L_Q$ $R_Q$

第 $1$ 行给出 NPC 的数量 $N$ ，满足 $1 \leq N \leq 10^5$ 。
接下来的 $N$ 行中，第 $i$ 行给出第 $i$ 个 NPC 的初始位置 $X_i$ （ $0 \leq X_i \leq 10^5$ ）和有符号的移动速度 $V_i$ （ $-10^5 \leq V_i \leq 10^5$ ）。
接下来的 $1$ 行给出问题的数量 $Q$ ，满足 $1 \leq Q \leq 10^5$ 。
接下来的 $Q$ 行中，第 $i$ 行给出一个问题，包含整数 $T_i$ （ $0 \leq T_i \leq 10^5$ ）、 $L_i$ （ $0 \leq L_i \leq 10^5$ ）、 $R_i$ （ $L_i \leq R_i \leq 10^5$ ）。

输出格式

输出共 $Q$ 行。
第 $i$ 行输出第 $i$ 个问题的答案。

输入输出样例

输入#1

输出#1

输入#2

4
0 50000
100000 -50000
0 2
100000 -3
6
0 50000 50000
1 50000 50000
2 50000 50000
20000 40000 40000
20001 39998 40001
20001 39997 40002

输出#2

输入#3

10
67812 -965
1766 93025
25587 -3294
14569 22
8830 203
50857 7
23407 -836
82660 80780
89781 1
86061 -1
10
97289 65405 94453
49386 73492 97497
75412 82840 94438
93076 43725 95471
18439 76630 93787
373 51319 92018
65554 30886 93533
66039 14298 95837
68359 90674 98196
31448 31879 98393

输出#3

说明/提示

样例解释 1

$0$ 到 $3$ 秒后，NPC 的位置如下图所示。

由 ChatGPT 4.1 翻译

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

首页