#1973. Robot
Robot
Robot
题目描述
标题: Robot - Problem - QOJ.ac
#4253. Robot
The problem was used in the following contests:
小 q 有 n 只机器人,一开始他把机器人放在了一条数轴上,第 i 只机器人在 ai 的位置上静止,而自己站在原点。
在这之后小 q 会执行一些操作,他想要命令一个机器人向左或者向右移动 x 格。但是机器人似乎听不清小 q 的命令,事实上它们会以每秒 x 格的速度匀速移动。
看着自己的机器人越走越远,小 q 很着急,他想知道当前离他(原点)最远的机器人有多远。
具体的操作以及询问见输入格式。注意,不同的机器人之间互不影响,即不用考虑两个机器人撞在了一起的情况。
输入格式
共有 m 个事件,输入将会按事件的时间顺序给出。
第一行两个正整数 n,m。
接下来一行 n 个整数,第 i 个数是 ai,表示第 i 个机器人初始的位置(初始移动速度为 0)。
接下来 m 行,每行行首是一个非负整数 ti,表示该事件点发生的时刻(以秒为单位)。第二个是一个字符串 S ,代表操作的种类。数字与字符串之间用一个空格隔开。接下来的输入按 S 的种类分类。
- 若 S 是 “
command”(不带引号),则接下来两个整数 ki,xi,表示小 q 对第 ki 个机器人执行了操作,该机器人的速度将会被重置,变为向数轴正方向每秒移动 xi 格(若 xi 为负数就相当于向数轴负方向每秒移动 |xi| 格)。保证 1≤ki≤n。 - 若 S 是 “
query”(不带引号),则你需要输出当前离原点最远的机器人有多远。
保证 t1≤t2≤t2≤⋯≤tm。
(注:若同一时间发生多次操作,则按读入顺序依次执行)
输出格式
对于每个 query 询问,输出一行,包含一个整数表示正确的答案。
C/C++ 输入输出 long long 时请用 %lld。由于本题数据量较大,建议不要使用 cin/cout 进行输入输出。
样例一
input
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
output
180
280
explanation
第一个命令执行时,各个机器人的位置为:−20,0,20,100。
第二个命令执行时,各个机器人的位置为:80,0,20,100。
第一个询问时,各个机器人的位置为:180,0,−80,100。
第三个命令执行时,各个机器人的位置为:280,0,−180,100。
第二个询问时,各个机器人的位置为:−20,0,−280,100。
限制与约定
设 command 的个数为 C,query 的个数为 Q。(所以 C+Q=m)
对于所有的事件满足 0≤ti≤109,对于所有的 command 满足 |xi|≤104。
对于所有的机器人满足 |ai|≤109。
所有测试数据的范围和特点如下表所示:
测试点编号 数据范围 特殊限制 1n,m≤2000无23n,m≤105−1≤xi≤14n,C≤105,Q≤5×105两个机器人发生碰面或者超越另一个的次数 ≤4×10556n,m≤105不会在 ti>0 时出现 command 操作78无9n,C≤105,Q≤5×10510
**时间限制:**1s
**空间限制:**256MB
来源
中国国家集训队互测2015 - By 张恒捷
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
180
280