Problem:


Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

1 ≦ N ≦ 200,000

(a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85



Sample input:
3
2 1 3


Sample output:
9

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class SegmentTree():
   
    def __init__(self,N,f,unit):
        self.f = f
        self.unit = unit
        self.N = N
        self.tree = [self.unit] * (2*self.N)
        #self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def debug(self):
        print(self.tree)

def main():
    N = int(input())
    A = list(map(int,input().split()))

    st = SegmentTree(N,max,-1)
    L = [-1] * N
    for i,a in enumerate(A):
        L[i] = st.query(0,a - 1)
        st.update(a - 1,i)
    
    st = SegmentTree(N,min,N)
    R = [N] * N
    for i in range(N - 1,-1,-1):
        R[i] = st.query(0,A[i] - 1)
        st.update(A[i] - 1,i)
    
    ans = sum((R[i] - i)*(i - L[i])*A[i] for i in range(N))
    print(ans) 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
R=0
N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  for j in range(i,N):
    R=R + min(L[i:j+1])
print(R)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

A = [(a, i) for i, a in enumerate(A, 1)]
A.sort()

n2i = [0] * (N + 1)
for a, i in A:
    n2i[a] = i

def num2index(a):
    print(a)
    if a == 0:
        return 1
    else:
        return n2i[a] + 1

bit = [0] * (N + 1)

def bit_add(bit, i, x):
    while i <= N:
        bit[i] += x
        i += i & - i

def bit_sum(bit, i):
    res = 0
    while i:
        res += bit[i]
        i -= i & -i
    return res
    
def bit_find_prev(i):
    if bit_sum(bit, i - 1) == 0:
        return 0
    else:
        ok = i - 1
        ng = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if bit_sum(bit, ok) - bit_sum(bit, mid):
                ng = mid
            else:
                ok = mid
        return ok

def bit_find_next(i):
    if bit_sum(bit, N) - bit_sum(bit, i) == 0:
        return N + 1
    else:
        ok = N
        ng = i
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if bit_sum(bit, mid) - bit_sum(bit, ng):
                ok = mid
            else:
                ng = mid
        return ok
    
answer = 0
for a, i in A:
    bit_add(bit, i, 1)
    #print(i, bit_find_prev(i), bit_find_next(i))
    answer += (bit_find_next(i) - i) * (i - bit_find_prev(i)) * a

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

def cal(A):
    if len(A) == 0:
        return 0
    else:
        pt,min_A = 0,2*10**5+1
        for i in range(len(A)):
            if min_A > A[i]:
                pt,min_A = i,A[i]

        A_left,A_right = A[:pt],A[pt+1:]
        ans = min_A * (len(A_left)+1) * (len(A_right)+1)
        return ans + cal(A_left) + cal(A_right)

def main():
    N = int(input())
    a = list(map(int,input().split()))

    setrecursionlimit(10**7)

    print(cal(a))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class SparseTable:
    def __init__(self, N, a):
        n = 1
        log = 0
        while n <= N:
            n <<= 1
            log += 1
        lookup = [[0] * log for _ in range(N)]
        for i in range(N):
            lookup[i][0] = a[i]
        for j in range(1, log):
            for i in range(N - (1 << j) + 1):
                lookup[i][j] = min(lookup[i][j-1], lookup[i + (1 << (j-1))][j-1])
        self.lookup = lookup
        self.log = log

    def query(self, l, r):
        lb, ub = 0, self.log + 1
        while ub - lb > 1:
            m = (lb + ub) // 2
            if (1 << m) <= r - l:
                lb = m
            else:
                ub = m
        return min(self.lookup[l][lb], self.lookup[r - (1 << lb)][lb])


N = int(input())
a = list(map(int, input().split()))
st = SparseTable(N, a)
left = [0] * N
for i in range(N):
    lb, ub = -1, i
    while ub - lb > 1:
        m = (lb + ub) // 2
        if st.query(m, i) < a[i]:
            lb = m
        else:
            ub = m
    left[i] = i - lb
right = [1] * N
for i in range(N-1):
    lb, ub = i, N+1
    while ub - lb > 1:
        m = (lb + ub) // 2
        if st.query(i, m) < a[i]:
            ub = m
        else:
            lb = m
    right[i] = lb - i
ans = 0
for i in range(N):
    ans += left[i] * right[i] * a[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

INF = 10**18

class RMQ:
    def __init__(self, size):
        n = 1
        while n < size:
            n <<= 1
        self.n = n
        self.data = [INF] * (2*n-1)

    def update(self, i, x):
        i += self.n-1  # the leaf
        self.data[i] = x
        while i > 0:
            i = (i-1)//2
            vl = self.data[i*2+1]
            vr = self.data[i*2+2]
            self.data[i] = min(vl, vr)

    def query(self, a, b, i=0, l=0, r=-1):
        if r == -1:
            r = self.n

        if r <= a or b <= l:
            return INF
        if a <= l and r <= b:
            return self.data[i]

        m = (l+r)//2
        vl = self.query(a, b, i*2+1, l, m)
        vr = self.query(a, b, i*2+2, m, r)
        return min(vl, vr)

N = int(input())
a = list(map(int, input().split()))
rmq = RMQ(N)
for i in range(N):
    rmq.update(i, a[i])
left = [0] * N
for i in range(N):
    lb, ub = -1, i
    while ub - lb > 1:
        m = (lb + ub) // 2
        if rmq.query(m, i) < a[i]:
            lb = m
        else:
            ub = m
    left[i] = i - lb
right = [1] * N
for i in range(N-1):
    lb, ub = i, N+1
    while ub - lb > 1:
        m = (lb + ub) // 2
        if rmq.query(i, m) < a[i]:
            ub = m
        else:
            lb = m
    right[i] = lb - i
ans = 0
for i in range(N):
    ans += left[i] * right[i] * a[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [-int(i) for i in input().split()]


class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - (1 << log)])


sp = SparseTable(a)
ans = 0
for i in range(n):
    mi = 0
    ma = i
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(mm, i) <= a[i]:
            ma = mm
        else:
            mi = mm + 1
    j = i - mi + 1

    mi = i - 1
    ma = n - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(i, mm + 1) <= a[i]:
            mi = mm
        else:
            ma = mm - 1
    k = mi - i + 1
    ans += j * k * a[i]
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
class Node:
    def __init__(self, key, value, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.value = value #ノードの値
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値
        self.value = None #lmaxの値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key, value): self.root = self.insert_sub(self.root, key, value)
    
    def insert_sub(self, t, key, value): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, value, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key, value)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key, value)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    ###############
    #Nodeの削除
    ###############
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: #nの右部分木が存在しない場合は左部分木を昇格させる
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    ###############
    #Nodeの探索
    ###############
    def search(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return True
        return False

    def getValue(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return t.value
        return None

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound
                

def solve(): #デバッグ用コード
    N = int(input())
    A = [int(a) for a in input().split()]
    Ai = dict()
    for i in range(N): Ai[A[i]] = i
    Tree = AVLTree()
    ini = Ai[1]
    Ans = 1 * (ini + 1) * (N - ini)
    Tree.insert(ini, 1)
    for i in range(2, N + 1):
        ai = Ai[i]
        Ans += i * (ai - Tree.lower_bound(ai, -1)) * (Tree.upper_bound(ai, N) - ai)
        Tree.insert(ai, i)
    print(Ans)
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
class Node:
    def __init__(self, key, value, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.value = value #ノードの値
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値
        self.value = None #lmaxの値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key, value): self.root = self.insert_sub(self.root, key, value)
    
    def insert_sub(self, t, key, value): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, value, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key, value)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key, value)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    ###############
    #Nodeの削除
    ###############
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: #nの右部分木が存在しない場合は左部分木を昇格させる
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    ###############
    #Nodeの探索
    ###############
    def search(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return True
        return False

    def getValue(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return t.value
        return None

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound
                

def solve(): #デバッグ用コード
    N = int(input())
    A = [int(a) for a in input().split()]
    Ai = [(A[i], i) for i in range(N)]
    Ai.sort()
    Tree = AVLTree()
    ini = Ai[0][1]
    Ans = 1 * (ini + 1) * (N - ini)
    Tree.insert(ini, 1)
    for i in range(2, N + 1):
        ai = Ai[i-1][1]
        Ans += i * (ai - Tree.lower_bound(ai, -1)) * (Tree.upper_bound(ai, N) - ai)
        Tree.insert(ai, i)
    print(Ans)
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
class Node:
    def __init__(self, key, value, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.value = value #ノードの値
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値
        self.value = None #lmaxの値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key, value): self.root = self.insert_sub(self.root, key, value)
    
    def insert_sub(self, t, key, value): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, value, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key, value)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key, value)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    ###############
    #Nodeの削除
    ###############
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: #nの右部分木が存在しない場合は左部分木を昇格させる
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    ###############
    #Nodeの探索
    ###############
    def search(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return True
        return False

    def getValue(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return t.value
        return None

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound
                

def solve(): #デバッグ用コード
    N = int(input())
    A = [int(a) for a in input().split()]
    Tree = AVLTree()
    ini = A.index(1)
    Ans = 1 * (ini + 1) * (N - ini)
    Tree.insert(ini, 1)
    for i in range(2, N + 1):
        ai = A.index(i)
        Ans += i * (ai - Tree.lower_bound(ai, -1)) * (Tree.upper_bound(ai, N) - ai)
        Tree.insert(ai, i)
    print(Ans)
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        tr = self.tree
        f = self.func
        while i > 0:
            s = f(s, tr[i])
            i -= i & -i
        return s

    def put(self, i, x):
        n = self.size
        tr = self.tree
        f = self.func
        while i <= n:
            y = tr[i]
            tr[i] = f(tr[i], x)
            if y == tr[i]:
                break
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        t = self.tree
        f = self.func
        while i > 0:
            s = f(s, t[i])
            i -= i & -i
        return s

    def put(self, i, x):
        n = self.size
        t = self.tree
        f = self.func
        while i <= n:
            t[i] = f(t[i], x)
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        while i > 0:
            s = self.func(s, self.tree[i])
            i -= i & -i
        return s

    def put(self, i, x):
        while i <= self.size:
            self.tree[i] = self.func(self.tree[i], x)
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


if __name__ == "__main__":
    N = int(input())
    P = list(map(int, input().split()))
    idx = {a: i for i, a in enumerate(P, start=1)}

    bit = BinaryIndexTree(N)
    ans = 0
    for i in range(1, N + 1):
        bit.add(idx[i], 1)
        s = bit.sum(idx[i])
        l = bit.lower_bound(s)-bit.lower_bound(s-1)
        r = bit.lower_bound(s+1) - idx[i]
        ans += i*l*r
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    pos = [0]*N
    
    for i,num in enumerate(a):
        pos[a[i]-1] = i+1

    l = [0,N+1]
    ans = 0
    for i in range(N):
        p = pos[i]
        ind = bisect.bisect(l,p)
        bisect.insort(l,p)
        ans += (p-l[ind-1])*(l[ind+1]-p)*(i+1)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ
import sys
input = sys.stdin.readline
N = int(input())
N+=1
a = [-1]+list(map(int, input().split( )))


N0 = 1
while N0<=N:
    N0*=2
INF = 10**10
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1],data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s,data[R-1])

        if L & 1:
            s = min(s,data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(N):
    update(i,a[i])
anss = 0
for i in range(1,N):
    ans = a[i]
    mx = N
    mn = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(i,md+1)
        if aj==a[i]:
            mn = md
        else:
            mx = md
    tmp = mn-i+1
    ans *= mn-i+1
    mn = 0
    mx = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(md,i+1)
        if aj==a[i]:
            mx = md
        else:
            mn = md
    ans*=i-mx+1
    anss+=ans
print(anss)

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ
from numpy import array
N = int(input())
N+=1
a = array([-1]+list(map(int, input().split( ))))


N0 = 1
while N0<=N:
    N0*=2
INF = 10**10
data = array([INF]*(2*N0))
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1],data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s,data[R-1])

        if L & 1:
            s = min(s,data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(N):
    update(i,a[i])
anss = 0
for i in range(1,N):
    ans = a[i]
    mx = N
    mn = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(i,md+1)
        if aj==a[i]:
            mn = md
        else:
            mx = md
    tmp = mn-i+1
    ans *= mn-i+1
    mn = 0
    mx = i
    while mx-mn>1:
        md = (mx+mn)//2
        aj = query(md,i+1)
        if aj==a[i]:
            mx = md
        else:
            mn = md
    ans*=i-mx+1
    anss+=ans
print(anss)