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: Wrong Answer

Solution code:
n = int(input())
a=[int(i) for i in input().split()]
s=[]
sa=0
s.append(a)
print(a)
for i in range(1,n):
  s.append([])
  for j in range(len(s[i-1])-1):
    if s[i-1][j]<s[i-1][j+1]:
        s[i].append(s[i-1][j])
        sa+=s[i-1][j]
    else:
        s[i].append(s[i-1][j+1])
        sa+=s[i-1][j+1]
print(sa)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
score = 0
mint = 200001
tmp = 0
for x in range(n-1,-1, -1):
	if mint > a[x]:
		mint = a[x]
		tmp = mint * (n-x)
	else :
		if a[x+1] > a[x]:
			tmplen = a.index(mint)-x
			tmp = a[x]*tmplen + mint * (n-a.index(mint))
		else :
			tmp += a[x]
	score += tmp

print(score)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
score = 0
mint = 200001
nmint = 200001
tmp = 0
for x in range(n-1,-1, -1):
	if mint > a[x]:
		mint = a[x]
		tmp = mint * (n-x)
	else :
		if nmint > a[x]:
			nmint = a[x]
			tmplen = a.index(mint)-a.index(nmint)
			tmp = nmint*tmplen + mint * (n-(x+tmplen))
		else :
			tmp += a[x]
	score += tmp

print(score)

Submission status: Wrong Answer

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

result = target = tmp = min_value = a[0]
min_index = 1

for index, i in enumerate(a[1:]):
    if target < i:
        tmp += i
        result += tmp
    else:
        if i < min_value:
            min_index = index + 2
            min_value = i
        tmp = i * (index + 2 - min_index) + min_value * min_index
        result += tmp
    target = i
print(result)

Submission status: Wrong Answer

Solution code:
input()
a = list(map(int, reversed(input().split())))

result = target = tmp = a[0]

for index, i in enumerate(a[1:]):
    if target < i:
        tmp += i
        result += tmp
    else:
        target = i
        tmp = i * (index + 2)
        result += tmp
print(result)

Submission status: Wrong Answer

Solution code:
a = list(map(int, reversed("1 3 2 4".split())))

result = target = tmp = a[0]

for index, i in enumerate(a[1:]):
    if target < i:
        tmp += i
        result += tmp
    else:
        target = i
        tmp = i * (index + 2)
        result += tmp
print(result)

Submission status: Wrong Answer

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

result = target = tmp = a[0]

for index, i in enumerate(a[1:]):
    if target < i:
        tmp += i
        result += tmp
    else:
        target = i
        tmp = i * (index + 2)
        result += tmp
print(result)

Submission status: Wrong Answer

Solution code:
N=input()
s=list(map(int,input()))

count=0
r=len(s)

while True:
    if r==0:
        break
    for k in reversed(range(1,r)):
        if s[k]<s[k-1]:
            print(s[k-1],s[k])
            hoge=s[k]
            s[k]=s[k-1]
            s[k-1]=hoge
            count+=1
        k-=1
    r-=1


n=len(s)
sum2=n*n*(1+n)/2.0

for i in range(1,len(s)):
    sum2-=i*(i+1)

#print(sum2)
print(sum2-count)

Submission status: Wrong Answer

Solution code:

N = int(input())
array = list(map(int, input().split())) 
sum = 0
for l in range(N):

       for r in range(N):
              if r+1+l>3:
                     break
              
              print(l,r+l+1)
              print( array[l:r+l+1])
              sum = sum + min(array[l:r+l+1])
print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split()
score = 0
for k in range(0,n):
	for l in range(k,n):
		score += int(min(a[k:l+1]))
print(score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
if __name__ == '__main__':
    n = int(input())
    a = input().split()
    ans = 0
    for l in range(n):
        for r in range(l, n):
            ans += int(min(a[l:r + 1]))
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = input().split()
ret = 0
b = [10 for k in range(N)]
for i, ai in enumerate(a):
    nai = int(ai)
    for j in range(0, i + 1):
        b[j] = min(b[j], nai)
        ret += b[j]
print(ret)

Submission status: Wrong Answer

Solution code:
st = input().split()
N = int(st[0])
a = st[1:]
ret = 0
b = [10 for k in range(N)]
for i, ai in enumerate(a):
    nai = int(ai)
    for j in range(0, i + 1):
        b[j] = min(b[j], nai)
        ret += b[j]
print(ret)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
a = input().split(" ")


it = itertools.combinations_with_replacement(sorted(a),2)
l = []
ans = 0
for i in it:
    print(a[int(i[0])-1:int(i[1])])
    ans += int(min(a[int(i[0])-1:int(i[1])]))
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
a = [x-1 for x in reads()]
b = [0] * N
for i in range(N):
  b[a[i]] = i

ps = [-1, N]
res = 0
for i in range(N):
  p = bisect(ps, b[i])
  print((ps[p] - b[i]), (b[i] - ps[p-1]), (i+1))
  res += (ps[p] - b[i]) * (b[i] - ps[p-1]) * (i+1)
  ps.insert(p, b[i])

print(res)

Submission status: Wrong Answer

Solution code:
a = input()
b = map(int,raw_input().split())
b.sort()
ans = 0

j = 1
for i in range(a-1):
  tmp = 0
  for k in range(j+1):
    tmp += b[k]
  ans += tmp
  j += 1
print ans

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [[int(a),i] for i,a in enumerate(input().split())]
A.sort()
bit = [0]*(n+1)

def sum(i):
    # [0, i) の要素の総和を返す
    s = 0
    while i>0:
        s += bit[i]
        i -= i & -i
    return s
# 0 index を 1 index に変更  転倒数を求めるなら1を足していく
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

# 総和がx以上になる位置のindex をbinary search
def bsearch(x):
    le = 0
    ri = 1<<(n.bit_length()-1)
    while ri > 0:
        if le+ri <= n and bit[le+ri]<x:
            x -= bit[le+ri]
            le += ri
        ri >>= 1
    return le+1 

ans = 0
for i in range(n):
    x,ind = A[i]
    s = sum(ind)
    if s == 0:
        l = 0
    else:
        l = bsearch(s)
    s2 = s+1
    if s2 > i:
        r = n
    else:
        r = bsearch(s2)-1
    ans += x*(r-ind)*(ind-l+1)
    add(ind,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n = int(input())
a = [[int(x),i] for i,x in enumerate(input().split())]
a.sort()
bit = BIT(n)

ans = 0

for i in range(n):
    x,ind = a[i]
    s = bit.sum(ind)
    if s == 0:
        l = 0
    else:
        l = bit.bsearch(s)
    s2 = s+1
    if s2 > i:
        r = n
    else:
        r = bit.bsearch(s2)-1
    ans += x*(r-ind)*(ind-l+1)
    bit.add(ind,1)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    for i, a in enumerate(A):
        l = r = i
        while l >= 0 and A[l] >= a: l -= 1
        while r < N and A[r] >= a: r += 1
        ans += a * (i - l) * (r - i)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
	"0-indexed apparently"
	
	def __init__(self, n):
		self.n = n
		self.data = [0] * (n+1)
		
	def point_add(self, index, value):
		index += 1
		while index <= self.n:
			self.data[index] += value
			index += index & -index
		
	def folded(self, r):
		"[0, r)"
		ret = 0
		while r > 0:
			ret += self.data[r]
			r -= r & -r
		return ret
		
	def bisect_left(self, value):
		index = 0
		k = 1 << ((self.n + 1).bit_length() - 1)
		while k > 0:
			if index + k <= self.n and self.data[index + k] < value:
				value -= self.data[index + k]
				index += k
			k >>= 1
		return index + 1
		
N = int(input())
As = list(map(int, input().split()))

A_inv = [0] * N
for i, A in enumerate(As):
	A_inv[A-1] = i
	
bit = BIT(N + 2)
bit.point_add(0, 1)
bit.point_add(N+1, 1)
ans = 0
for A, index in enumerate(A_inv):
	A += 1
	index += 1
	v = bit.folded(index)
	ans += A * (bit.bisect_left(v+1) - index - 1) * (index - bit.bisect_left(v) + 1)
	#print(A, ans)
	bit.point_add(index, 1)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*aa = map(int, open(0).read().split())

ans = 0
for i in range(n):
    tmp = float('inf')
    for j in range(i,n):
        tmp = min(tmp,aa[j])
        ans += tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  def func(l,i):
    ret=l*(l+1)//2
    ret-=i*(i+1)//2
    ret-=(l-i-1)*(l-i)//2
    return ret
  dn={a[i]:i+1 for i in range(n)}
  from bisect import bisect_left,insort
  space=[0,n+1]
  ans=0
  for i in range(1,n+1):
    t=dn[i]
    tl=bisect_left(space,t)
    l=space[tl-1]
    r=space[tl]
    lg=r-l-1
    ans+=func(lg,t-l-1)*i
    insort(space,t)
  print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  now=n
  for j in range(i,n):
    now=min(now,a[j])
    ans+=now
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
def func(l,i):
    ret=l*(l+1)//2
    ret-=i*(i+1)//2
    ret-=(l-i-1)*(l-i)//2
    return ret
dn={a[i]:i+1 for i in range(n)}
from bisect import bisect_left,insort
space=[0,n+1]
ans=0
for i in range(1,n+1):
    t=dn[i]
    tl=bisect_left(space,t)
    l=space[tl-1]
    r=space[tl]
    lg=r-l-1
    ans+=func(lg,t-l-1)*i
    insort(space,t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class Binary_Indexed_Tree:
    #Binary_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    #A1 ~ Aiまでの和 O(logN)
    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x

def main():
    n = int(ipt())
    ans = 0
    a = [int(i) for i in ipt().split()]
    pl = [-1]*(n+1)
    for i,ai in enumerate(a):
        pl[ai] = i+1

    bt = Binary_Indexed_Tree(n)

    for i in range(1,n+1):
        pi = pl[i]
        bi = bt.query(pl[i])
        lb = bt.lower_bound(bi)
        ub = bt.upper_bound(bi)
        ans += (pi-lb)*(ub-pi+1)*i
        bt.update(pi,1)

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = 0
    a = [int(i) for i in ipt().split()]
    pl = [-1]*(n+1)
    for i,ai in enumerate(a):
        pl[ai] = i+1

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(1,n+1):
        pi = pl[i]
        ll = 0
        lr = pi
        bi = BIT_query(pl[i])
        while ll != lr:
            mid = ll+(lr-ll)//2
            if BIT_query(mid) == bi:
                lr = mid
            else:
                ll = mid+1
        rl = pi
        rr = n
        while rl != rr:
            mid = rl+(rr-rl+1)//2
            if BIT_query(mid) == bi:
                rl = mid
            else:
                rr = mid-1
#        print("a",rl,lr)
        ans += (pi-lr)*(rl-pi+1)*i
        BIT_update(pi,1)

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
d=[0,n+1]
for i in range(n):
  c[a[i]-1]=i+1
ans=0
for i in range(n):
  j=bisect.bisect_left(d,c[i])
  ans+=(c[i]-d[j-1])*(d[j]-c[i])*(i+1)
  d=d[:j]+[c[i]]+d[j:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in range(N):
    dic[A[i]]=i+1
bit=BIT(N)
ans=0
for i in range(1,N+1):
    d=dic[i]
    bit.add(d,1)
    c=bit.get(d+1)
    L=bit.lowerbound(c-1)
    R=bit.lowerbound(c+1)
    ans+=(R-d)*(d-L)*i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

cand = [(0,N)]

ans = 0
while cand:
    temp = []
    for l,r in cand:
        m = min(A[l:r])
        i = A[l:r].index(m) + l
        ans += m * (i-l+1) * (r-i)
        if l < i:
            temp.append([l,i])
        if i+1 < r:
            temp.append([i+1,r])
    cand = temp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# segment tree verify
class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree(N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])
B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)
    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree(N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])
B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)
    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# segment tree verify
class SegTree():
    # 1-indexed
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree([N+1]*N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])

B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)

    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Submission status: Time Limit Exceeded

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

def main():
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)

		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return max(x, y)

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret

		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)

		# seg確認用
		def BIT_print(self):
			print(self.BIT)
		
	N = int(input())
	a = list(map(int,input().split()))
	ans=[i+1 for i in range(N)]
	left_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a):
	    ans[num-1] *= i + 1 - left_bit.BIT_query(num)
	    left_bit.BIT_update(num, i+1)
	right_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    ans[num-1] *= i + 1 - right_bit.BIT_query(num)
	    right_bit.BIT_update(num, i+1)
	
	print(sum(ans))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# bitの改造
import sys
input = sys.stdin.readline


class BIT:
    # 1,,,,,,,Nまでの数値を扱える
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        # i番目のところまで要素を足し合わせる
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        # i 番目のところに要素を足し合わせる
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        # i番目からj番目までの要素の合計値を数える(1<=i<=j<=Nという制約がついているけど)
        return self.to_sum(j)-self.to_sum(i-1)

    def bisect_right(self, i):
        # i 番目から　次に初めて1増えるところまでの最大の値 j を求める
        l = i
        r = self.n
        if self.get(i, r) == r-i+1:
            return r
        while r-l > 1:
            M = (l+r)//2
            if self.get(i, M) < M-i+1:
                r = M
            else:
                l = M
        return l

    def bisect_left(self, i):
        # i 番目から最後に初めて1減るところまでの最小のjを求める
        l = 1
        r = i
        if self.get(l, i) == i+1-l:
            return l
        while r-l > 1:
            M = (r+l)//2
            if self.get(M, i) < i+1-M:
                l = M
            else:
                r = M
        return r


def main():
    N = int(input())
    a = list(map(int, input().split()))
    b = [(a[i], i+1) for i in range(N)]
    b.sort(reverse=True)
    tree = BIT(N)
    ans = 0

    for value, index in b:
        tree.add(index, 1)

        ans += (tree.bisect_right(index)-index+1) * \
            (index-tree.bisect_left(index)+1)*value

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# bitの改造
import sys
input = sys.stdin.readline


class BIT:
    # 1,,,,,,,Nまでの数値を扱える
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        # i番目のところまで要素を足し合わせる
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        # i 番目のところに要素を足し合わせる
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        # i番目からj番目までの要素の合計値を数える(1<=i<=j<=Nという制約がついているけど)
        return self.to_sum(j)-self.to_sum(i-1)

    def bisect_right(self, i):
        # i 番目から　次に初めて1増えるところまでの最大の値 j を求める
        l = i
        r = self.n
        if self.get(i, r) == r-i+1:
            return r
        while r-l > 1:
            M = (l+r)//2
            if self.get(i, M) < M-i+1:
                r = M
            else:
                l = M
        return l

    def bisect_left(self, i):
        # i 番目から最後に初めて1減るところまでの最小のjを求める
        l = 1
        r = i
        if self.get(l, i) == i+1-l:
            return l
        while r-l > 1:
            M = (r+l)//2
            if self.get(M, i) < i+1-M:
                l = M
            else:
                r = M
        return r


N = int(input())
a = list(map(int, input().split()))
b = [(a[i], i+1) for i in range(N)]
b.sort(reverse=True)
tree = BIT(N)
ans = 0

for value, index in b:
    tree.add(index, 1)

    ans += (tree.bisect_right(index)-index+1) * \
        (index-tree.bisect_left(index)+1)*value

print(ans)