Dynamic maximum sum P59380


Statement
 

pdf   zip

thehtml

In this problem, you have to efficiently keep a vector V with n integers. There is just one update operation: given any position i between 0 and n − 1, and an integer x, set V[i] = x. Appart from that, you have to repeatedly report the maximum sum of all the consecutive subsequences of the current vector.

Input

Input consists of several cases. Every case begins with n, followed by the initial content of V, followed by n operations, each one with a pair i x. You can assume 1 ≤ n ≤ 105, 0 ≤ i < n, and −1012x ≤ 1012.

Output

For every case, print n+1 numbers: the maximum sum of consecutive elements inside the vector before the first update, and also after every update. Print a line with 10 dashes at the end of each case.

Public test cases
  • Input

    3
    10 5 10
    0 -3
    1 -8
    0 20
    
    1
    -300
    0 0
    
    3
    1000000000000 1000000000000 1000000000000
    1 -1
    2 -1000000000000
    2 2
    

    Output

    25
    15
    10
    22
    ----------
    0
    0
    ----------
    3000000000000
    1999999999999
    1000000000000
    1000000000001
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++