Problem : 246 - Mountain

Problem Statistics

Solved Member: 15　　Submission: 90　　User Tried: 16

Statement:

遊樂園已經開始運行一個嶄新的模擬過山車。模擬的軌道由n 段鐵軌組成，並且首尾相連。第一段鐵軌從高度0開始。操作員Byteman能通過調整連續幾段的鐵軌高度來改造這條軌道。在被改造的一段前面的鐵軌高度不受影響。每一次鐵軌被調整。後面的軌必須升起或降低來保持連通，並保證起點高度為0。下頁舉例說明軌道改造過程。

每次開始時車都有足夠能量到達高度h。也就是說，只要軌道的高度不超過h車就一直開下去, 甚至直到結束。

給出每天的運行和改造情況, 為每次運行計算在車停止前，到達的鐵軌數。鐵軌以一個n個數的數列形式表示，一個數對應一段鐵軌。第i個di表示在第i段鐵軌上的高度變化。也就是說，在到達鐵軌i前，如果車的高度是h，那麼經過鐵軌i後，高度變為h+di。最初軌道是一條水平線。就是說對於所有的i都是di=0。運行和改造交錯進行。每個改造用三個數表示: a ， b 和 D。表示從a到b(包括a,b)的所有di改為di=D。每次運行給定一個數字h ——車能到達的最大高度。

Input:Output:

輸入的第一行包括一個正整數n，表示鐵軌的數目，1 ≤ n ≤ 1000000000。下面的行包括改造和運行，各有一個標識符：

改造：一個字母I，和整數a,b,D(1 ≤ a ≤ b ≤ n, -1000000000 ≤ D ≤ 1000000000),中間用一個空格隔開。
運行：一個字母Q，和一個整數h(0 ≤ h ≤ 1000000000)，用一個空格隔開。
結束符號：一個字母E，表示輸入結束。

你可以假設任意時刻任意鐵軌的高度在[0, 1000000000]區間內。輸入不超過100000行。

50%的數據n滿足1 ≤ n ≤ 20000且輸入不超過1000行。

第i行需包含一個整數，即第i次運行經過的鐵軌數。

Sample Input:Sample Output:

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

4
1
0
3

HINT:

Source:

IOI 2005

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	4
2	1000ms	262144kb	4
3	1000ms	262144kb	4
4	1000ms	262144kb	4
5	1000ms	262144kb	4
6	1000ms	262144kb	4
7	1000ms	262144kb	4
8	1000ms	262144kb	4
9	1000ms	262144kb	4
10	1000ms	262144kb	4
11	1000ms	262144kb	4
12	1000ms	262144kb	4
13	3000ms	262144kb	4
14	3000ms	262144kb	4
15	3000ms	262144kb	4
16	3000ms	262144kb	4
17	3000ms	262144kb	4
18	3000ms	262144kb	4
19	3000ms	262144kb	4
20	3000ms	262144kb	4
21	3000ms	262144kb	5
22	3000ms	262144kb	5
23	3000ms	262144kb	5
24	3000ms	262144kb	5