Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Foehn Phenomena

  

In the Kingdom of IOI, the wind always blows from sea to land. There are $N + 1$ spots numbered from $0$ to $N$. The wind from Spot $0$ to Spot $N$ in order. Mr. JOI has a house at Spot $N$. The altitude of Spot $0$ is $A_0 = 0$, and the altitude of Spot $i$ ($1 \leq i \leq N$) is $A_i$.
  

  

The wind blows on the surface of the ground. The temperature of the wind changes according to the change of the altitude. The temperature of the wind at Spot $0$, which is closest to the sea, is $0$ degree. For each $i$ ($0 \leq i \leq N - 1$), the change of the temperature of the wind from Spot $i$ to Spot $i + 1$ depends only on the values of $A_i$ and $A_{i+1}$ in the following way:
  

  

    
If $A_i 
  

  

    The 16th Japanese Olympiad in Informatics (JOI 2016/2017)
Final Round
  



Sample input:
3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5


Sample output:
-5
-7
-13
-13
-18

Submission status: Time Limit Exceeded

Solution code:
n, q, s, t = map(int, input().split())
a = [int(input()) for _ in range(n + 1)]
for _ in range(q):
    l, r, x = map(int, input().split())
    for i in range(l, r + 1):
        a[i] += x
    temp = 0
    for i in range(1, n + 1):
        temp += (a[i - 1] - a[i]) * s if a[i] > a[i - 1] else (a[i - 1] - a[i]) * t
    print(temp)

Submission status: Accepted

Solution code:
N, Q, S, T = map(int, input().split())
A = [int(input()) for i in range(N+1)]
C = 0
for i in range(N):
    if A[i] < A[i+1]:
        C += S * (A[i] - A[i+1])
    else:
        C += T * (A[i] - A[i+1])
def add(k, x):
    if x >= 0:
        if B[k] <= 0:
            if B[k] + x <= 0:
                return - T * x
            return T * B[k] - S * (B[k] + x)
        return - S * x
    if B[k] >= 0:
        if B[k] + x >= 0:
            return - S * x
        return S * B[k] - T * (B[k] + x)
    return - T * x

B = [A[i+1] - A[i] for i in range(N)]
ans = []
for q in range(Q):
    l, r, x = map(int, input().split())
    C += add(l-1, x); B[l-1] += x
    if r < N:
        C += add(r, -x); B[r] -= x
    ans.append(C)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N, Q, S, T = map(int, input().split())
A = [int(input()) for i in range(N + 1)]
diff = [A[i + 1] - A[i] for i in range(N)]

def calc(v):
    if v > 0:
        return -S * v
    else:
        return -T * v

ret = 0
for i in range(N):
    ret += calc(diff[i])
    
for i in range(Q):
    a, b, c = map(int, input().split())
    ret -= calc(diff[a - 1])
    diff[a - 1] += c
    ret += calc(diff[a - 1])
    if b != N:
        ret -= calc(diff[b])
        diff[b] -= c
        ret += calc(diff[b])
    print(ret)

Submission status: Accepted

Solution code:
n, q, s, t = map(int, input().split())
a = [int(input()) for _ in range(n + 1)]
for i in range(1, n + 1)[::-1]:
    a[i] -= a[i - 1]
count = 0
for i in range(n + 1):
    count -= a[i] * s if a[i] > 0 else a[i] * t
for _ in range(q):
    l, r, x = map(int, input().split())
    count += a[l] * s if a[l] > 0 else a[l] * t
    a[l] += x
    count -= a[l] * s if a[l] > 0 else a[l] * t
    if r < n:
        count += a[r + 1] * s if a[r + 1] > 0 else a[r + 1] * t
        a[r + 1] -= x
        count -= a[r + 1] * s if a[r + 1] > 0 else a[r + 1] * t
    print(count)

Submission status: Accepted

Solution code:
n, q, s, t = map(int, input().split())
a_lst = [int(input()) for _ in range(n + 1)]
diff = [a_lst[i + 1] - a_lst[i] for i in range(n)]
temp = sum([-d * s if d > 0 else -d * t for d in diff])
def score(d):
  if d > 0:
    return -s * d
  else:
    return -t * d
for _ in range(q):
  l, r, x = map(int, input().split())
  a = diff[l - 1]
  diff[l - 1] += x
  temp += score(diff[l - 1]) - score(a)
  if r < n:
    b = diff[r]
    diff[r] -= x
    temp += score(diff[r]) - score(b)
  print(temp)