시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 10 | 7 | 7 | 77.778% |
Stjepan is programming a robot arm that can use a chalk to draw on a blackboard located in a standard coordinate plane (x coordinate increases to the right, y coordinate increases upwards).
The robot arm’s plan is an array of precisely N vectors (x1, y1), . . . , (xN, yN) where each xi and yi are even integers. The plan is executed by the robot arm starting from point (1, 1) and making N steps: in the i th step, the arm moves the chalk from the current point (x, y) straight to the point (x + xi, y + yi). Therefore, the robot arm is drawing a kind of a broken line in the coordinate plane, and the segments of that broken line are the given vectors.
While Stjepan is devising and changing his plan, sometimes he wants to know how many times the chalk will go over the coordinate axes. Write a programme that will simulate the process of changing the plan and that will give answers to Stjepan’s queries.
The layout of the plan on each ‘Q‘ command in the second test case. The dotted line marks the segment that was most recently changed.
Let us assume that Stjepan wrote down his plan in a text file that consists of N lines – the ith line contains the vector (xi, yi). Initially, Stjepan’s cursor is located at the first line of the file. Your programme should simulate the following commands:
The first line of input contains the integer N – the number of vectors in the plan. The ith of the following N lines contains two even integers xi and yi separated by a single space – the coordinates of the ith vector in the initial plan.
The following line contains the integer M – the number of commands which execution you need to simulate. Each of the following M lines contains a single command. A command is either one of the uppercase letters ‘B’, ‘F’ or ‘Q’ or an expression in the form ‘C nx ny’ where nx and ny are even integers described in the task.
For each ‘Q‘ command from the input, you must output its result in a single line. The results need to be printed in the order which the commands appear in the input.
The following holds for all the initial vectors and all the new vectors in ‘C‘ commands in each subtask: −500 ≤ xi, yi, nx, ny ≤ 500.
번호 | 배점 | 제한 |
---|---|---|
1 | 9 | 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 1 000 |
2 | 35 | 1 ≤ N ≤ 50 000, 1 ≤ M ≤ 100 000 |
3 | 56 | 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 300 000 |
6 2 2 2 -6 -2 -4 -6 4 10 -10 -8 12 16 Q C -4 -4 F F Q F C 6 -2 B B B Q C 0 6 Q F C -8 4 Q
4 4 3 1 5
5 6 2 0 -6 -2 2 -6 -8 4 0 12 Q C 4 4 Q F F F C -6 -2 Q B B C -4 -6 Q
3 5 5 4