문제
동현이가 경영하는 산악 유원지에서는 레일의 경사를 마음대로 조절할 수 있는 획기적인 스타일의 롤러 코스터를 선보였다.
롤러 코스터가 다니는 선로는 n개의 레일로 이루어져 있으며, 각 레일의 끝은 다음 레일의 시작과 연결된 형태이다.
첫 레일의 시작은 고도가 항상 0이나, 각 레일의 끝부분은 롤러 코스터 운영자인 동현이는 높이를 얼마든지 조절할 수 있다.
레일의 시작과 끝의 높이가 다르면 롤러 코스터가 다니는 길에 경사가 생기는 것이다.
경사 조절은 이어져 있는 여러 레일을 상대로 일괄적으로 할 수 있다.
이 경우, 높이가 바뀐 레일의 바로 다음 레일들은 시작 부분이 이전 레일의 끝과 연결된 상태를 유지하게끔,
자신의 기울기(경사)는 유지한 채로 고도만 그대로 하강하거나 상승한다.
한편, 이 트랙을 다니는 열차는 고도가 0인 초기 위치에서 고도가 h인 지점까지 오를 수 있는 추진력을 한 번만 받은 후,
그 뒤부터는 그 높이에 다다르거나 레일을 모두 지날 때까지 관성으로 다닌다. 물론 레일에는 마찰이 없다고 가정한다.
초기에는 모든 레일들이 고도가 0인 위치에서 수평을 이루고 있다.
그러나 동현이는 각 레일의 고도도 마음대로 조정하고, 그 상태에서 열차 운행도 초기 추진력을 무작위로 줘 가며 한다.
해당 상태에서 열차를 h까지 갈 수 있는 힘을 받아서 출발했을 때, 열차가 어느 레일까지 갈 수 있는지를 계산하는 프로그램을 작성하시오.
입력
첫 줄에는 레일의 개수 n이 있다. (1 <= n <= 10억) 그리고 다음부터는 순차적으로 레일의 경사를 재 조정하거나 그 상태에서 열차를 운행한 기록이 한 줄에 하나씩 들어있으며, 마지막으로 입력의 끝임을 나타내는 표시로 입력이 끝난다. 즉, 각 줄에는 다음 중 한 가지 형태의 정보가 있다.
테스트 케이스들의 절반은 1 <= n <= 20,000이며, 입력량 역시 1,000줄 이내이다.
• 경사 조정 : 알파벳 'I', 그리고 정수 a, b, D (1 <= a <= b <= n, -10억 <= D <= 10억). a번 레일의 시작 부분의 고도를 기준점으로 하여 b번 레일의 끝 구간까지를, 경사가 D인 일직선이 되게 한다. b번 이후의 레일들은 b번 레일 끝 부분의 고도에 맞춰 높이가 평행 이동 된다.
• 열차 운행 : 알파벳 'Q', 그리고 열차가 받은 추진력으로 올라갈 수 있는 최대 높이 h (0 <= h <=10억)
• 입력의 끝임을 나타내는 알파벳 'E' 경사를 조정하는 과정에서 레일 한쪽 끝의 고도 역시 0에서 10억 사이임이 보장된다. 또한 입력량은 10만 줄을 넘지 않는다.
출력
명령이 들어왔을 때 레일 상태의 변화를 잘 파악하고 있다가,
Q 명령이 들어오면 그만한 힘을 받은 열차가 몇째 레일까지 완주할 수 있는지 계산하여 그 레일 번호를 출력하면 된다.
예제
4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E
4
1
0
3
힌트
출처
IOI 2005 day1 3
로그인해야 코드를 작성할 수 있어요.