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:



# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x or y

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
#%%
idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i


ans = 0
seg = SegTree(N,[0]*N,segfunc,0)

def judge(l,r):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res:
        return False
    else:
        return True


for idx in idxlist:    
    ng_l = -1
    ng_r = N
    left = idx
    while abs(left-ng_l)>1:
        mid = (left+ng_l)//2
        if judge(idx,mid):
            left = mid
        else:
            ng_l = mid
    
    right = idx
    while abs(ng_r-right)>1:
        mid = (right+ng_r)//2
        if judge(idx,mid):
            right = mid
        else:
            ng_r = mid
    
    ans += A[idx]*(idx-left+1)*(right-idx+1)
    seg.update(idx,1)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:



# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x|y

# import sys
# input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
#%%
idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i


ans = 0
seg = SegTree(N,[0]*N,segfunc,0)

def judge(l,r):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res:
        return False
    else:
        return True


for idx in idxlist:    
    ng_l = -1
    ng_r = N
    left = idx
    while abs(left-ng_l)>1:
        mid = (left+ng_l)//2
        if judge(idx,mid):
            left = mid
        else:
            ng_l = mid
    
    right = idx
    while abs(ng_r-right)>1:
        mid = (right+ng_r)//2
        if judge(idx,mid):
            right = mid
        else:
            ng_r = mid
    
    ans += A[idx]*(idx-left+1)*(right-idx+1)
    seg.update(idx,1)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree:
    def __init__(self, N, f=max, id=0):
        self.N = N
        self.bit = [id] * (self.N+1)
        self.f = f
        self.id = id

    def query(self, i):
        res = self.id
        while i > 0:
            res = self.f(res, self.bit[i])
            i -= i & -i
        return res

    def update(self, i, x):
        while i <= self.N:
            self.bit[i] = self.f(self.bit[i], x)
            i += i & -i

def main():
    N,*A=map(int, open(0).read().split())
    L,R=[0]*N,[0]*N
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A):
        L[a-1]=i-bit.query(a)
        bit.update(a, i)
    bit=BinaryIndexedTree(N, max, -1)
    for i,a in enumerate(A[::-1]):
        R[a-1]=i-bit.query(a)
        bit.update(a, i)
    print(sum(L[i]*R[i]*(i+1) for i in range(N)))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self,n):
    self.N = n
    self.data = [0]*(N+1)
  def bit_add(self,i,a):
    j = i+1
    while j<=N:
      self.data[j] += a
      j += j&-j
  def bit_sum(self,i):
    m = 0
    j = i+1
    while j>0:
      m += self.data[j]
      j -= j&-j
    return m
  def bit_search(self,x):
    i = 0
    m = 0
    j = 1<<(self.N.bit_length()-1)
    while j:
      if i+j<=N and self.data[i+j]+m<=x:
        i += j
        m += self.data[i]
      j >>= 1
    return i
N, *A = map(int, open(0).read().split())
bit = BIT(N)
ntoi = [0]*(N+1)
ans = 0
for i, a in enumerate(A):
  ntoi[a] = i
for i in range(1,N+1):
  j = ntoi[i]
  L = bit.bit_sum(j)
  R = N-L-1
  if L!=0:
    a = bit.bit_search(L-1)
  else:
    a = -1
  if R!=0:
    b = bit.bit_search(L)
  else:
    b = N
  ans += (j-a)*(b-j)*i
  bit.bit_add(j,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    X = SI()
    d = defaultdict(int)
    for s in X:
        if s=="T" and d["S"]>=1:
            d["S"] -=1
        else:
            d[s] += 1
    ans = d["S"] + d["T"]
    print(ans)
    return

def examB():
    # じゅっぴーさんの
    # https://juppy.hatenablog.com/entry/2019/02/11/%E8%9F%BB%E6%9C%AC_python_AVL%E6%9C%A8_%E6%A4%9C%E7%B4%A2%E6%8B%A1%E5%BC%B5_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
    ###############################################################################
    # root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
    # root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
    # y.to_s(): 頂点yのdataを出力
    # y.left_s(): 頂点yのleftを出力(ない場合はNone)
    # root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
    # root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力
    ################################################################################
    class Avltree:
        def __init__(self, key=None):
            self.key = key
            self.left = None
            self.right = None
            self.balance = "Even"

        def search(self, key):
            if self.key == None:
                return None
            if self.key > key:
                if self.left == None:
                    return None
                else:
                    return self.left.search(key)
            if self.key < key:
                if self.right == None:
                    return None
                else:
                    return self.right.search(key)
            return self  # self.key == keyの場合

        def search_lower(self, key, key_lower):
            if self.key == None:
                return key_lower
            if self.key > key:
                if self.left == None:
                    return key_lower
                else:
                    return self.left.search_lower(key, key_lower)
            if self.key < key:
                key_lower = self.key
                if self.right == None:
                    return key_lower
                else:
                    return self.right.search_lower(key, key_lower)
            # self.key == keyの場合
            if self.left == None:
                return key_lower
            else:
                if key_lower == None:
                    return self.left.end_higher(self.left.key)
                else:
                    return max(key_lower, self.left.end_higher(self.left.key))

        def search_higher(self, key, key_higher):
            if self.key == None:
                return key_higher
            if self.key > key:
                key_higher = self.key
                if self.left == None:
                    return key_higher
                else:
                    return self.left.search_higher(key, key_higher)
            if self.key < key:
                if self.right == None:
                    return key_higher
                else:
                    return self.right.search_higher(key, key_higher)
            # self.key == keyの場合
            if self.right == None:
                return key_higher
            else:
                if key_higher == None:
                    return self.right.end_lower(self.right.key)
                else:
                    return min(key_higher, self.right.end_lower(self.right.key))

        def end_lower(self, end_lower_key):
            if self.left == None:
                return end_lower_key
            else:
                end_lower_key = self.left.key
                return self.left.end_lower(end_lower_key)

        def end_higher(self, end_higher_key):
            if self.right == None:
                return end_higher_key
            else:
                end_higher_key = self.right.key
                return self.right.end_higher(end_higher_key)

        def DoubleRightRotation(self):
            tl = self.left
            self.left = tl.right.right
            tl.right.right = self  # selfはそのノード
            tlr = tl.right
            tl.right = tlr.left
            tlr.left = tl
            if tlr.balance == "Left":
                tlr.right.balance = "Right"
                tlr.left.balance = "Even"
            elif tlr.balance == "Right":
                tlr.right.balance = "Even"
                tlr.left.balance = "Left"
            elif tlr.balance == "Even":
                tlr.right.balance = "Even"
                tlr.left.balance = "Even"
            tlr.balance = "Even"
            return tlr

        def DoubleLeftRotation(self):
            tr = self.right
            self.right = tr.left.left
            tr.left.left = self
            trl = tr.left
            tr.left = trl.right
            trl.right = tr
            if trl.balance == "Right":
                trl.left.balance = "Left"
                trl.right.balance = "Even"
            elif trl.balance == "Left":
                trl.left.balance = "Even"
                trl.right.balance = "Right"
            elif trl.balance == "Even":
                trl.left.balance = "Even"
                trl.right.balance = "Even"
            trl.balance = "Even"
            return trl

        def SingleLeftRotation(self):
            tr = self.right
            tr.balance = "Even"
            self.balance = "Even"
            self.right = tr.left
            tr.left = self
            return tr

        def SingleRightRotation(self):
            tl = self.left
            tl.balance = "Even"
            self.balance = "Even"
            self.left = tl.right
            tl.right = self
            return tl

        def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
            if p.left == self:
                p.left = v
            else:
                p.right = v

        def insert(self, key):  # rootでのみ呼ばれる挿入
            if self.key == None:  # rootを含むrotationはしないことにする。
                self.key = key
                return self
            if key < self.key:
                if self.left == None:
                    self.left = Avltree(key)
                else:
                    self.left.insertx(self, key)
            elif key > self.key:
                if self.right == None:
                    self.right = Avltree(key)
                else:
                    self.right.insertx(self, key)
            else:  # key == self.key:
                pass  # do not overwrite

        def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
            if self.key > key:
                if self.left == None:
                    self.left = Avltree(key)
                else:
                    if not self.left.insertx(self, key):  # 左の木が生長しなければ、
                        return False  # 成長しない
                if self.balance == "Right":
                    self.balance = "Even"
                    return False
                elif self.balance == "Even":
                    self.balance = "Left"
                    return True  # 成長した
                elif self.balance == "Left":
                    if self.left.balance == "Right":
                        self.replace(p, self.DoubleRightRotation())
                    elif self.left.balance == "Left":
                        self.replace(p, self.SingleRightRotation())
                    return False  # rotationを行うと成長しない
            if self.key < key:
                if self.right == None:
                    self.right = Avltree(key)
                else:
                    if not self.right.insertx(self, key):
                        return False
                if self.balance == "Left":
                    self.balance = "Even"
                    return False
                elif self.balance == "Even":
                    self.balance = "Right"
                    return True
                elif self.balance == "Right":
                    if self.right.balance == "Left":
                        self.replace(p, self.DoubleLeftRotation())
                    elif self.right.balance == "Right":
                        self.replace(p, self.SingleLeftRotation())
                    return False
            return False  # self.key == keyの時は何もしないので成長もしない

        def to_s(self):
            return self.key

        def left_s(self):
            if self.left == None:
                return None
            return (self.left).key

        def right_s(self):
            if self.right == None:
                return None
            return (self.right).key

    ################################################################
    N = I()
    A = LI()
    lst = [0] * N
    for i in range(N):
        lst[A[i]-1] = i
    AVL = Avltree()
    ans = 0
    for a in range(1,N+1):
        i = lst[a-1]
        l = AVL.search_lower(i,None)
        r = AVL.search_higher(i,None)
        AVL.insert(i)
        #print(l,r)
        if l==None:
            l = -1
        if r==None:
            r = N
        ans += (i-l)*(r-i)*a
        #print(l,r,i,ans)
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index

    def search_r(self, l, r):
        # l <= x < r
        ng = l - 1
        ok = r - 1
        while ng + 1 < ok:
            mid = (ng + ok) // 2
            if self.interval_sum(l, mid + 1):
                ok = mid
            else:
                ng = mid
        return ok

    def search_l(self, l, r):
        # l <= x < r
        ng = r
        ok = l
        while ok + 1 < ng:
            mid = (ok + ng) // 2
            if self.interval_sum(mid, ng):
                ok = mid
            else:
                ng = mid
        return ok

n = I()
A = LI()
val_idx = {A[j]:j+1 for j in range(n)}
bit = BIT(n + 2)
bit.add(n + 1, 1)
bit.add(0, 1)
ans = 0
for k in range(1, n + 1):
    idx = val_idx[k]
    l = bit.search_l(0, idx)
    r = bit.search_r(idx + 1, n + 2)
    ans += (r - idx) * (idx - l) * k
    bit.add(idx, 1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for k,v in enumerate(a):
  left = 1
  right = 1
  for i in range(k-1,-1,-1):
    if v > a[i]:
      break
    left += 1
  for i in range(k+1,n):
    if v > a[i]:
      break
    right += 1
  ans += left * right * v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for k,v in enumerate(a):
  left = 1
  right = 1
  for i in range(k-1,-1,-1):
    if v > a[i]:
      break
    left += 1
  for i in range(k+1,n):
    if v > a[i]:
      break
    right += 1
  ans += left * right * v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, raw_input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)

    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)

    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)
    
    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))


    class RangeMinimumQuery:
        def __init__(self, n, inf=2 ** 31 - 1):
            self.n = 1 << (n - 1).bit_length()
            self.INF = inf
            self.segtree = [self.INF] * (2 * self.n)

        # i番目の値(0-indexed)をxに変更
        def update(self, i, x):
            i += self.n
            self.segtree[i] = x
            while i > 0:
                i //= 2
                self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

        # [l, r)のmin
        def query(self, l, r):
            L, R = l + self.n, r + self.n
            R = min(R, len(self.segtree))
            s = self.INF
            while L < R:
                if L & 1:
                    s = min(s, self.segtree[L])
                    L += 1

                if R & 1:
                    s = min(s, self.segtree[R - 1])
                    R -= 1

                L >>= 1
                R >>= 1

            return s


    # 番兵を設置
    A = [0] + A + [0]
    N = N + 2


    # セグ木を初期化
    RMQ = RangeMinimumQuery(N)
    for i, a in enumerate(A):
        RMQ.update(i, a)


    # r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
    # l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
    r_indexes = [None] * N
    l_indexes = [None] * N


    # 右側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, N - 1
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(i, m + 1):
                ok = m
            else:
                ng = m

        r_indexes[i] = ok + 1

    # 左側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, 0
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(m, i + 1):
                ok = m
            else:
                ng = m

        l_indexes[i] = ok - 1


    # 答えを計算
    ans = 0
    for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
        ans += a * (i - l) * (r - i)

    print(ans)

Submission status: Time Limit Exceeded

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


class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree))
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


# 番兵を設置
A = [0] + A + [0]
N = N + 2


# セグ木を初期化
RMQ = RangeMinimumQuery(N)
for i, a in enumerate(A):
    RMQ.update(i, a)


# r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
# l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
r_indexes = [None] * N
l_indexes = [None] * N


# 右側についてにぶたん := iからm内の区間最小値がai以上か？
for i, a in enumerate(A[1: -1], start=1):
    ok, ng = i, N - 1
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2

        if a <= RMQ.query(i, m + 1):
            ok = m
        else:
            ng = m

    r_indexes[i] = ok + 1

# 左側についてにぶたん := iからm内の区間最小値がai以上か？
for i, a in enumerate(A[1: -1], start=1):
    ok, ng = i, 0
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2

        if a <= RMQ.query(m, i + 1):
            ok = m
        else:
            ng = m

    l_indexes[i] = ok - 1


# 答えを計算
ans = 0
for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
    ans += a * (i - l) * (r - i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)
maxcost = 10**10
n = int(input())
num = [ int(v) for v in input().split() ]
pos = sorted([ (v, i) for i, v in enumerate(num,1) ])
pos = [ i[1] for i in pos ]
ln = len(bin(n-1))-1
ln2 = 2**(ln-1)
segtree = [ maxcost for i in range(2**ln-1) ]
#最小値用

def update_tomin(tree, p, q=1):
    p += 2**(ln-1)-2
    while p >= 0:
        tree[p] = min(tree[p], q)
        p = (p-1)//2

def getmin(tree,a,b,k=0,l=0,r=ln2):
    if r <= a or b <= l:
        return maxcost
    elif a <= l and r <= b:
        return tree[k]
    else:
        return min( getmin(tree,a,b,2*k+1,l,(l+r)//2), getmin(tree,a,b,2*k+2,(l+r)//2,r) )

for i, v in enumerate(num):
    update_tomin(segtree,i+1,v)

def divconq(a, b):
    if a == b:
        return num[a-1]
    else:
        m = getmin(segtree,a-1,b)
        k = pos[m-1]
        s = m * (b-k+1) * (k-a+1)
        if k == a:
            return s + divconq(a+1, b)
        elif k == b:
            return s + divconq(a, b-1)
        else:
            return s + divconq(a, k-1) + divconq(k+1, b)

print(divconq(1,n))