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: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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

    idx = {}
    for i in range(N):
        idx[a[i]] = i

    left_idx, right_idx = list(range(N + 1)), list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        i = idx[a]
        l, r = left_idx[i], right_idx[i]
        ans += (i - l + 1) * (r - i + 1) * a

        left_idx[r + 1] = l
        right_idx[l - 1] = r

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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

    idx = {}
    for i in range(N):
        idx[a[i]] = i

    ans = 0
    left_idx, right_idx = list(range(N + 2)), list(range(N + 2))
    for a in range(N, 0, -1):
        i = idx[a]
        l, r = left_idx[i], right_idx[i]

        ans += a * (i - l + 1) * (r - i + 1)
        left_idx[r + 1] = l
        right_idx[l - 1] = r

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import defaultdict

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

cnt = 0
d = [0] * (N + 2)
for i in range(N):
    d[a[i]] = i


l = list(range(N + 2))
r = list(range(N + 2))

# print(a)
for i in range(N, 0, -1):
    di = d[i]
    cnt += i * (r[di] - di + 1) * (di - l[di] + 1)
    r[l[di] - 1] = r[di]
    l[r[di] + 1] = l[di]
    # print(i)
    # print(r)
    # print(l)
# print(r)
# print(l)
print(cnt)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
def f():
    s=[(0,-1)]
    x=[0]*(n+1)
    for i,j in enumerate(a):
        while s[-1][0]>j:s.pop()
        x[j]=i-s[-1][1]
        s.append((j,i))
    return x
l=f()
a.reverse()
r=f()
print sum([i*l[i]*r[i] for i in a])

Submission status: Accepted

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# a = int(input())
# b, c = map(int, input().split())
# s = input()


par = [0]*202020
size = [0]*202020

def find(x):
	if par[x] == x:
		return x
	else:
		par[x] = find(par[x])
		return par[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	res = size[x] * size[y]
	size[x] += size[y]
	par[y] = x
	return res

# main
n = int(input())
for i in range(202020):
	par[i] = i
	size[i] = 1

a = [0] + list(map(int, input().split()))
b = [0]*(n+1)
for i in range(1, n+1):
	b[a[i]] = i

ans = 0
for j in reversed(range(1, n+1)):
	i = b[j]
	ans += a[i]
	if i - 1 >= 1 and a[i-1] > a[i]:
		ans += unite(i-1, i) * a[i]
	if i + 1 <= n and a[i+1] > a[i]:
		ans += unite(i+1, i) * a[i]
print(ans)

Submission status: Accepted

Solution code:
input()
A=map(int,raw_input().split())
def f():
 s=[(0,-1)];p=A*2
 for i,a in enumerate(A):
  while a<s[-1][0]:s.pop()
  p[a]=i-s[-1][1];s+=[(a,i)]
 return p
l=f()
A.reverse()
r=f()
print sum(a*l[a]*r[a]for a in A)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n=int(raw_input())
a=map(int,raw_input().split())
p=[0]*(n+1)
for i in xrange(n):
    p[a[i]]=i

uf=UnionFind(n+1)
ans=0
for j in xrange(n,0,-1):
    i=p[j]
    tmp=1
    if i>=1 and a[i]<a[i-1]:
        tmp*=uf.tree_weight(a[i-1])+1
        uf.unite(a[i],a[i-1])
    if i<n-1 and a[i]<a[i+1]:
        tmp*=uf.tree_weight(a[i+1])+1
        uf.unite(a[i],a[i+1])
    ans+=j*tmp
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    l = list(range(n+2))
    r = list(range(n+2))
    b = [0]*(n+2)
    for i, x in enumerate(a, 1):
        b[x] = i
    c = 0
    for i in range(n,0,-1):
        bi = b[i]
        c += i * (r[bi] - bi + 1) * (bi - l[bi] + 1)
        r[l[bi]-1] = r[bi]
        l[r[bi]+1] = l[bi]
    return c

print(f())

Submission status: Accepted

Solution code:
ss = raw_input()
X=map(int, raw_input().split(' '))
N = []
S = []

dR = dict()
for n in range(len(X)) + [len(X)]:
    if n >= len(X): k = -100
    else: 
        #print n
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dR[S[-1][0]] = n - S[-1][0]
        S.pop()

    S.append((n, k))

dL = dict()
for n in list(reversed(range(len(X)))) + [-1]:
    if n < 0: k = -100
    else: 
        k = X[n]
    while len(S) > 0 and k < S[-1][1]:
        dL[S[-1][0]] = abs(n - S[-1][0])
        S.pop()
    S.append((n, k))


ts = 0
for n in xrange(len(X)):
    left = dL[n]
    right = dR[n]
    ts += ((left-1) * (right-1) + left + right - 1) * X[n]

print ts

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    L = range(n + 2)
    R = range(n + 2)
    b = [0] * (n + 2)
    L[n+1] = R[n+1] = n
    L[0] = R[0] = 1
    for i, x in enumerate(a, 1):
        b[x] = i
    s = 0
    for i in xrange(n, 0, -1):
        j = b[i]
        s += i * (R[j] - j + 1) * (j - L[j] + 1)
        R[L[j]-1] = R[j]
        L[R[j]+1] = L[j]
    print s
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
a = map(int, raw_input().split())

aso = [N]*N
q = [a[0]]
for i in xrange(1, N):
    while q and q[-1] > a[i]:
        aso[q[-1] - 1] = i
        q.pop()
    q.append(a[i])
dso = [-1]*N
q = [a[-1]]
for i in xrange(N - 2, -1, -1):
    while q and q[-1] > a[i]:
        dso[q[-1] - 1] = i 
        q.pop()
    q.append(a[i])

ans = 0
for i in xrange(N):
    ans += a[i] * (aso[a[i] - 1] - i)*(i - dso[a[i] - 1])
print ans

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  int a[N];
  int tmptmp;
  for(int i=0;i<N;++i) {
    cin>>tmptmp;
    tmptmp--;
    a[tmptmp] = i;
  }
  set<ll> st;
  st.insert(-1);
  st.insert(N);
  auto tmp=st.begin(), tmp1=st.begin(), tmp2=st.begin();
  ll ans = 0;
  for(ll i=0;i<N;++i) {
    st.insert(a[i]);
    tmp = st.find(a[i]);
    tmp1 = st.find(a[i]);
    tmp1--;
    tmp2 = st.find(a[i]);
    tmp2++;
    ans += (i+1)*(*tmp-*tmp1)%mod*(*tmp2-*tmp)%mod;
    ans %= mod;
  }
  cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg?P`QD5d7~`ER=Fu@8pF3DAIcpIZBMHw=|bXvi9iPcTKFlmIf4eW_H|<JU~x@XC@OGFv^az8u6sdG8??Rf}u`NQx%Xw({*y5LB4-+AE?>+jZWc@q6*xT+vpKlUzFd&<jL}obo!Go&Q@+hukO8i^f<_4HG&E$Tr#mo?eU716Rb1c;{akPsWvabx{*wift-!$_MqVe$B5o8WDx2kSxzU^TASn_;Q3{vXb|=ljtz7k)%%8PC{OZwg8B$0bP@N+v$t?pkQL)t)E+3I#@X>(k*3uy&>56S?}6MF*&yQ}F#<2UK|vZ&ZEErW^;t4jS6Rzy69n9%ygk%=u;=2Bsv=&8P5jSKVl%{xQ)S!@{afc|+vln!vD&)N<4SVkrJBgeIHE}6#L0FRzK9ITpz4$#DzX7Rua@aL<hw`H?_^O$_66`A&C>")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Runtime Error

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

def main():
	
	# SegmentTree Class
	class SegmentTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = 2**(size-1).bit_length()
			self.default = default
			self.seg = [default]*(2*self.size)

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

		# update
		def update(self,k,x):
			k += self.size
			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])

		# query([p,q)のsegfunc)
		def query(self,p,q):
			if q <= p:
				return self.default
			p += self.size-1;q += self.size-2
			ret = self.default
			while q-p > 1:
				if p&1 == 0:
					ret = self.segfunc(ret,self.seg[p])
				if q&1 == 1:
					ret = self.segfunc(ret,self.seg[q])
					q -= 1
				p = p//2
				q = (q-1)//2
			ret = self.segfunc(self.segfunc(ret,self.seg[p]),self.seg[q])
			return ret

		# seg確認用
		def seg_print(self):
			print(self.seg)
		
	N = int(input())
	a = list(map(int,input().split()))
	ans=[i+1 for i in range(N)]
	left_seg = SegmentTree(N, 0)
	for i, num in enumerate(a):
	    ans[num-1] *= i + 1 - left_seg.query(0,num)
	    left_seg.update(num-1, i+1)
	right_seg = SegmentTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    ans[num-1] *= i + 1 - right_seg.query(0,num)
	    right_seg.update(num-1, i+1)
	
	print(sum(ans))

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
a=list(map(int,input().split()))
A=[a[0]+a[0]<a[1]-a[0]>a[1]]+a+[a[-1]+a[-1]<a[-2]-a[-1]>a[-2]]
valley=0
peak=1
dp=deque()
for i in range(1,n+1):
  if A[i-1]<A[i]>A[i+1]:
    dp.append((i-1,peak))
  elif A[i-1]>A[i]<A[i+1]:
    dp.append((i-1,valley))
l,lf=dp.popleft()
r,rf=dp.popleft()
if lf == peak:
  ans=a[0]
else:
  ans=a[0]*(r+1)
for i in range(1,n-1):
  if r == i:
    t,tf=r,rf
    r,rf=dp.popleft()
    if tf == valley:
      ans+=a[i]*(i-l+1)*(r-i+1)
    else:
      ans+=a[i]
    l,lf=t,tf
  else:
    if lf == valley:
      ans+=a[i]*(r-i+1)
    else:
      ans+=a[i]*(i-l+1)
if rf == valley:
  ans+=a[-1]*(n-l)
else:
  ans+=a[-1]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
a=list(map(int,input().split()))
A=[a[0]+a[0]<a[1]-a[0]>a[1]]+a+[a[-1]+a[-1]<a[-2]-a[-1]>a[-2]]
valley=0
peak=1
dp=deque()
for i in range(1,n+1):
  if A[i-1]<A[i]>A[i+1]:
    dp.append((i-1,peak))
  elif A[i-1]>A[i]<A[i+1]:
    dp.append((i-1,valley))
l,lf=dp.popleft()
r,rf=dp.popleft()
if lf == peak:
  ans=a[0]
else:
  ans=a[0]*(r+1)
print(ans)
for i in range(1,n-1):
  if r == i:
    t,tf=r,rf
    r,rf=dp.popleft()
    if tf == valley:
      ans+=a[i]*(i-l+1)*(r-i+1)
    else:
      ans+=a[i]
    l,lf=t,tf
  else:
    if lf == valley:
      ans+=a[i]*(r-i+1)
    else:
      ans+=a[i]*(i-l+1)
if rf == valley:
  ans+=a[-1]*(n-l)
else:
  ans+=a[-1]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
a=list(map(int,input().split()))
A=[a[0]+a[0]<a[1]-a[0]>a[1]]+a+[a[-1]+a[-1]<a[-2]-a[-1]>a[-2]]
valley=0
peak=1
dp=deque()
for i in range(1,n+1):
  if A[i-1]<A[i]>A[i+1]:
    dp.append((i-1,peak))
  elif A[i-1]>A[i]<A[i+1]:
    dp.append((i-1,valley))
l,lf=dp.popleft()
r,rf=dp.popleft()
if lf == peak:
  ans=a[0]
else:
  ans=a[0]*(r+1)
for i in range(1,n-1):
  if r == i:
    t,tf=r,rf
    r,rf=dp.popleft()
    if rf == valley:
      ans+=a[i]*(i-l+1)*(r-i+1)
    else:
      ans+=a[i]
  	l,lf=t,tf
  else:
    if lf == valley:
      ans+=a[i]*(r-i+1)
    else:
      ans+=a[i]*(i-l+1)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

def cal(A):
    if len(A) == 0:
        return 0
    else:
        B = sorted(A)
        C = [B[len(B)-1-i] for i in range(len(B))]
        if A == B or A == C:
            if A == B:
                output = 0
                for i in range(len(A)):
                    output += (A[i] * (len(A)-i))
                return output
            else:
                output = 0
                for i in range(len(A)):
                    output += (A[N-i-1] * (len(A)-i))
                return output
        else:
            min_A = B[0]
            for i in range(len(A)):
                if A[i] == min_A: #最小
                    pt = i
                    break
            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: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

vector<vector<int>> lookup;
int L;

void build_sparse_table(int N, vector<ll>& a) {
    int n = 1;
    L = 0;
    while (n <= N) {
        n <<= 1;
        L++;
    }
    lookup = vector<vector<int>>(N, vector<int>(L));
    REP(i, N) {
        lookup[i][0] = a[i];
    }
    for (int j = 1; j < L; j++) {
        REP(i, N - (1 << j) + 1) {
            lookup[i][j] = min(lookup[i][j-1], lookup[i + (1 << (j-1))][j-1]);
        }
    }
}

int query(int l, int r) {
    int lb = 0, ub = L + 1;
    while (ub - lb > 1) {
        int m = (lb + ub) / 2;
        if ((1 << m) < r - l) lb = m;
        else ub = m;
    }
    return min(lookup[l][lb], lookup[r - (1 << lb)][lb]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    vector<ll> a(N);
    REP(i, N) cin >> a[i];
    build_sparse_table(N, a);

    vector<ll> left(N);
    REP(i, N) {
        int lb = -1, ub = i;
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (query(m, i) < a[i]) lb = m;
            else ub = m;
        }
        left[i] = i - lb;
    }
    vector<int> right(N);
    REP(i, N) {
        int lb = i, ub = N+1;
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (query(i, m) < a[i]) ub = m;
            else lb = m;
        }
        right[i] = lb - i;
    }
    ll ans = 0;
    REP(i, N) ans += left[i] * right[i] * a[i];
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
n+=2
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num

l=list(map(int,input().split()))
p=[]

n-=2
for i in range(n):
    p.append([l[i],i+1])
p.sort(key=lambda x:x[0])
ans=0
update(0,1)
update(n+1,1)
for i in range(n):
    update(p[i][1],1)
    x=query(0,p[i][1])
    ok=n+1
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x-1:
            ng=m
            else:
            ok=m
    left=ok
    ok=n+1
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x-1:
            ng=m
            else:
            ok=m
    right=ok
    ans+=(i+1)*(l[i][1]-left)*(right-l[i][1])
print(ans)

Submission status: Runtime Error

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: Runtime Error

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(list(enumerate(a)), key=lambda x: -x[1])
    L = [i for i in range(n+2)]  # 連結成分のうち一番左のindex
    R = [i for i in range(n+2)]  # 連結成分のうち一番右のindex
    ans = 0
    for i, j in a:  # 1-indexなので1ずれる
        print(L, R)
        M = R[i+1]  # 連結成分の最大値
        m = L[i+1]  # 連結成分の最小値
        ans += j*(M-i)*(i+2-m)  # 計算
        R[m-1] = M  # 連結成分の左端の更新
        L[M+1] = m  # 連結成分の右端の更新
    print(ans)


main()

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
def main():
  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
        
    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)
        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)
        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
        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):
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key):
        if self.key == None:
            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):
        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
        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

    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=int(input())
 a=list(map(int,input().split()))
 ans=0
 l=[0]*n
 for i in range(n):
   l[a[i]-1]=i
 root=Avltree()
 root.insert(-1)
 root.insert(n)
 for i in range(n):
   root.insert(l[i])
   ans+=(i+1)*(l[i]-root.search_lower(l[i],None))*(root.search_higher(l[i],None)-l[i])
 print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
INF = float('inf')

def query(a, b, k, l, r, st):
  if r <= a or b <= l:
    return INF
  if a <= l and r <= b:
    return st[k]
  else:
    k *= 2
    t = (l + r) // 2
    vl = query(a, b, k + 1, l, t)
    vr = query(a, b, k + 2, t, r)
    return min(vl, vr)

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

  n = 1 << N.bit_length()
  st = [INF] * (2 * n - 1)

  for i in range(N):
    k = i + n - 1
    st[k] = a[i]
    while k > 0:
      k = (k - 1) // 2
      st[k] = min(st[k * 2 + 1], st[k * 2 + 2])

  result = 0
  for l in range(N):
    for r in range(l, N):
      result += query(l, r + 1, 0, 0, n)
  print(result)

main()

Submission status: Runtime Error

Solution code:
INF = float('inf')

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

st = [INF] * ((1 << N.bit_length()) - 1)

for i in range(N):
  k = i + N - 1
  st[k] = a[i]
  while k > 0:
    k = (k - 1) // 2
    st[k] = min(st[k * 2 + 1], st[k * 2 + 2])

def query(a, b, k, l, r):
  if r <= a or b <= l:
    return INF
  if a <= l and r <= b:
    return st[k]
  else:
    vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
    vr = query(a, b, k * 2 + 2, (l + r) // 2, r)
    return min(vl, vr)

result = 0
for l in range(N):
  for r in range(l, N):
    result += query(l, r + 1, 0, 0, N)
print(result)

Submission status: Runtime Error

Solution code:
import bisect


class BTreeNode:
    def __init__(self):
        self.key = []
        self.child = []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_right(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect.bisect_right(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_left(ptr.key, key)
            if i != 0:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect.bisect_left(ptr.key, key)
        if i != 0:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 512
            if not ptr.child:
                bisect.insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                        ret = BTreeNode()
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            else:
                i = bisect.bisect(ptr.key, key)
                temp = insert_rec(ptr.child[i])
                if temp is not None:
                    ptr.key.insert(i, temp.key.pop(-1))
                    ptr.child.insert(i, temp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            return None
        temp = insert_rec(self.root)
        if temp is not None:
            root = BTreeNode()
            root.key = [temp.key.pop(-1)]
            root.child = [temp, self.root]
            self.root = root

    def dump(self):
        def dump_rec(ptr, dep):
            for _ in range(0, dep):
                print("  ", end="")
            print(ptr.key)
            for c in ptr.child:
                dump_rec(c, dep + 1)
        dump_rec(self.root, 0)
        print("")


def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=BTree()
    t.insert(0)
    t.insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        insert(t.v)
    print(c)
main()