Three Sequences (Codeforces 1406D)
Tags: Greedy, data structures

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$.You have to construct two sequences of integers $$$b$$$ and $$$c$$$ with length $$$n$$$ that satisfy:  for every $$$i$$$ ($$$1\leq i\leq n$$$) $$$b_i+c_i=a_i$$$  $$$b$$$ is non-decreasing, which means that for every $$$1<i\leq n$$$, $$$b_i\geq b_{i-1}$$$ must hold  $$$c$$$ is non-increasing, which means that for every $$$1<i\leq n$$$, $$$c_i\leq c_{i-1}$$$ must hold You have to minimize $$$\max(b_i,c_i)$$$. In other words, you have to minimize the maximum number in sequences $$$b$$$ and $$$c$$$.Also there will be $$$q$$$ changes, the $$$i$$$-th change is described by three integers $$$l,r,x$$$. You should add $$$x$$$ to $$$a_l,a_{l+1}, \ldots, a_r$$$. You have to find the minimum possible value of $$$\max(b_i,c_i)$$$ for the initial sequence and for sequence after each change.

Input: The first line contains an integer $$$n$$$ ($$$1\leq n\leq 10^5$$$).The secound line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq i\leq n$$$, $$$-10^9\leq a_i\leq 10^9$$$).The third line contains an integer $$$q$$$ ($$$1\leq q\leq 10^5$$$).Each of the next $$$q$$$ lines contains three integers $$$l,r,x$$$ ($$$1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$$$), desribing the next change. 

Output: Print $$$q+1$$$ lines.On the $$$i$$$-th ($$$1 \leq i \leq q+1$$$) line, print the answer to the problem for the sequence after $$$i-1$$$ changes.

Note: In the first test:  The initial sequence $$$a = (2, -1, 7, 3)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,2,2,-2)$$$ is a possible choice.  After the first change $$$a = (2, -4, 4, 0)$$$. Two sequences $$$b=(-3,-3,5,5),c=(5,-1,-1,-5)$$$ is a possible choice.  After the second change $$$a = (2, -4, 6, 2)$$$. Two sequences $$$b=(-4,-4,6,6),c=(6,0,0,-4)$$$ is a possible choice. 

Sample Inputs:
4
2 -1 7 3
2
2 4 -3
3 4 2

6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

1
0
2
1 1 -1
1 1 -1

Sample Outputs:
5
5
6

3
3
3
1

0
0
-1

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, arr) = (readInt(), readList())
    q = readInt()
    d = [0] * n
    v = 0
    for i in range(1, n):
        d[i] = arr[i] - arr[i - 1]
        v += max(d[i], 0)
    print((arr[0] + v + 1) // 2)
    for _ in range(q):
        (l, r, x) = readInts()
        l -= 1
        r -= 1
        if l == 0:
            arr[0] += x
        else:
            v -= max(d[l], 0)
            d[l] += x
            v += max(d[l], 0)
        if r + 1 < n:
            v -= max(d[r + 1], 0)
            d[r + 1] -= x
            v += max(d[r + 1], 0)
        print((v + arr[0] + 1) // 2)
    return
solve()

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n + 2)
    sp = 0
    sn = 0
    for i in range(1, n):
        b[i] = a[i] - a[i - 1]
        if b[i] < 0:
            sn += b[i]
        else:
            sp += b[i]
    b[0] = a[0]
    print((b[0] + sp + 1) // 2)
    for q in range(int(input())):
        (l, r, x) = map(int, input().split())
        if l > 1:
            if b[l - 1] >= 0:
                sp -= b[l - 1]
            b[l - 1] += x
            if b[l - 1] >= 0:
                sp += b[l - 1]
        else:
            b[l - 1] += x
        if r < n:
            if b[r] >= 0:
                sp -= b[r]
            b[r] -= x
            if b[r] >= 0:
                sp += b[r]
        else:
            b[r] -= x
        print((b[0] + sp + 1) // 2)
solve()

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n + 2)
    sp = 0
    for i in range(1, n):
        b[i] = a[i] - a[i - 1]
        if b[i] > 0:
            sp += b[i]
    b[0] = a[0]
    print((b[0] + sp + 1) // 2)
    for q in range(int(input())):
        (l, r, x) = map(int, input().split())
        if l > 1:
            if b[l - 1] > 0:
                sp -= b[l - 1]
            b[l - 1] += x
            if b[l - 1] > 0:
                sp += b[l - 1]
        else:
            b[l - 1] += x
        if r < n:
            if b[r] > 0:
                sp -= b[r]
            b[r] -= x
            if b[r] > 0:
                sp += b[r]
        else:
            b[r] -= x
        print((b[0] + sp + 1) // 2)
solve()