Sanggeun's Robot
Time limit1sMemory limit128 MB
Track a moving point's total Manhattan distance to many fixed checkpoints after each move, requiring separate sorted-prefix-sum structures for x and y coordinates updated dynamically.
- Level
Medium6 of 10
- Topics
- Prefix sum, Binary search, Sorting, Implementation
- Solved
- No attempts yet
Problem
Sanggeun wants to test a new robot on a test track. The track is a two-dimensional plane, and the robot starts at (0, 0). He sends the robot a sequence of commands, each one of S, J, I, and Z.
If the robot is currently at (x, y), each command means the following move.
To check whether the robot moves correctly, Sanggeun installed N fixed checkpoints on the track. After each command, the robot reports the sum of the Manhattan distances from its current position to all checkpoints.
Compute the value reported by the robot immediately after each command.
Input
The first line contains the number of checkpoints N and the number of commands M. (1 <= N <= 100,000, 1 <= M <= 300,000)
Each of the next N lines contains the coordinates x and y of one checkpoint. Every coordinate is an integer whose absolute value is at most 1,000,000. Multiple checkpoints may have the same coordinates; in that case, each checkpoint must be counted separately.
The last line contains the length-M command string sent to the robot. The string consists only of S, J, I, and Z.
Output
Print exactly M lines. On the i-th line, print the sum of the Manhattan distances from the robot's current position to all checkpoints immediately after executing the i-th command.