Also Try Minecraft (Codeforces 1709B)
Tags: Implement, data structures

You are beta testing the new secret Terraria update. This update will add quests to the game!Simply, the world map can be represented as an array of length $$$n$$$, where the $$$i$$$-th column of the world has height $$$a_i$$$.There are $$$m$$$ quests you have to test. The $$$j$$$-th of them is represented by two integers $$$s_j$$$ and $$$t_j$$$. In this quest, you have to go from the column $$$s_j$$$ to the column $$$t_j$$$. At the start of the quest, you are appearing at the column $$$s_j$$$.In one move, you can go from the column $$$x$$$ to the column $$$x-1$$$ or to the column $$$x+1$$$. In this version, you have Spectre Boots, which allow you to fly. Since it is a beta version, they are bugged, so they only allow you to fly when you are going up and have infinite fly duration. When you are moving from the column with the height $$$p$$$ to the column with the height $$$q$$$, then you get some amount of fall damage. If the height $$$p$$$ is greater than the height $$$q$$$, you get $$$p - q$$$ fall damage, otherwise you fly up and get $$$0$$$ damage.For each of the given quests, determine the minimum amount of fall damage you can get during this quest.

Input: The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5; 1 \le m \le 10^5$$$) — the number of columns in the world and the number of quests you have to test, respectively.The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the height of the $$$i$$$-th column of the world.The next $$$m$$$ lines describe quests. The $$$j$$$-th of them contains two integers $$$s_j$$$ and $$$t_j$$$ ($$$1 \le s_j, t_j \le n; s_j \ne t_j$$$), which means you have to move from the column $$$s_j$$$ to the column $$$t_j$$$ during the $$$j$$$-th quest.Note that $$$s_j$$$ can be greater than $$$t_j$$$.

Output: Print $$$m$$$ integers. The $$$j$$$-th of them should be the minimum amount of fall damage you can get during the $$$j$$$-th quest completion.


Sample Inputs:
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2

Sample Outputs:
2
10
0
7
3
1

Solution (Python):
import sys, math, itertools, functools, collections
input = sys.stdin.readline

def solve():
    (n, m) = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    right = [0] * n
    left = [0] * n
    x = 0
    for i in range(1, n):
        if a[i - 1] > a[i]:
            x += a[i - 1] - a[i]
        right[i] = x
    x = 0
    for i in range(n - 2, -1, -1):
        if a[i + 1] > a[i]:
            x += a[i + 1] - a[i]
        left[i] = x
    for i in range(m):
        (p, q) = map(int, input().split(' '))
        if p < q:
            print(right[q - 1] - right[p - 1])
        else:
            print(left[q - 1] - left[p - 1])
solve()

Solution (Python):
import sys
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from collections import Counter
from collections import defaultdict as dd
from collections import deque
from datetime import datetime
from functools import cmp_to_key as ctk
from heapq import heappop, heappush
from io import BytesIO, IOBase
from itertools import permutations
from math import ceil, gcd, log, sqrt
from os import path

def ii():
    return int(input())

def si():
    return input().rstrip()

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

def li():
    return list(mi())

def li_of_str():
    return map(str, input().split())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
    return ord(i) - ord('0')
file = 1

def ceil(a, b):
    return (a + b - 1) // b

def solve():
    test = 1
    for t in range(test):
        (n, m) = mi()
        a = li()
        dp = [0] * n
        pd = [0] * n
        for i in range(1, n):
            if a[i] < a[i - 1]:
                dp[i] = dp[i - 1] - a[i] + a[i - 1]
            else:
                dp[i] = dp[i - 1]
        for i in range(n - 2, -1, -1):
            if a[i + 1] > a[i]:
                pd[i] = pd[i + 1] + a[i + 1] - a[i]
            else:
                pd[i] = pd[i + 1]
        ans = []
        for i in range(m):
            (low, high) = mi()
            if low > high:
                ans.append(pd[high - 1] - pd[low - 1])
            else:
                ans.append(dp[high - 1] - dp[low - 1])
        for i in ans:
            print(i)
if __name__ == '__main__':
    if file:
        if path.exists('input.txt'):
            sys.stdin = open('input.txt', 'r')
            sys.stdout = open('output.txt', 'w')
        else:
            input = sys.stdin.readline
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
board = list(map(int, input().split()))
board = [0] + board
cumul_forward = [0]
cumul_backward = [0]
for (a, b) in zip(board[:-1], board[1:]):
    if a - b < 0:
        cumul_backward.append(cumul_backward[-1] + b - a)
        cumul_forward.append(cumul_forward[-1])
    else:
        cumul_backward.append(cumul_backward[-1])
        cumul_forward.append(cumul_forward[-1] + a - b)
for _ in range(m):
    (st, ed) = map(int, input().split())
    if st < ed:
        print(cumul_forward[ed] - cumul_forward[st])
    else:
        print(cumul_backward[st] - cumul_backward[ed])