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 itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


A = np.array(A)
pos = np.zeros(N + 1, dtype=int)
pos[0] = -1
pos[A] = np.arange(N + 1)

ans = 0
lefts = [0] * N
rights = [0] * N
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        # 右とつながった
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        # 左とつながった
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (p - left + 1) * (right - p + 1) * i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def gutyocu():
    ans = 0
    for i, j in itertools.combinations_with_replacement(range(N), r=2):
        ans += min(A[i: j + 1])
    return ans


A = np.array(A)
pos = np.arange(N + 1)
pos[0] = -1
pos[A] = np.arange(N + 1)

ans = 0
lefts = np.arange(N)
rights = np.arange(N)
for i in reversed(range(1, N + 1)):
    p = pos[i]
    if p + 1 < N and A[p + 1] > i:
        # 右とつながった
        right = rights[p + 1]
    else:
        right = p
    if p - 1 >= 0 and A[p - 1] > i:
        # 左とつながった
        left = lefts[p - 1]
    else:
        left = p
    lefts[right] = left
    rights[left] = right
    ans += (abs(left - p) + 1) * (abs(right - p) + 1) * i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])

l=1
while l<2*(n+2)-1:
	l*=2
l-=1
seg=[True]*l
seg[0]=False

def update(i):
	if seg[i]:
		seg[i]=False
		update((i-1)//2)

update((l-1)//2)
update((l-1)//2+n+1)

def search_left(i,j):
	if j==1:
		if i%2==1:
			return search_left((i-1)//2,1)
		else:
			if seg[i-1]:
				return search_left((i-1)//2,1)
			else:
				return search_left(i-1,0)
	else:
		if i<l//2:
			return search_left(2*i+2-seg[2*i+2],0)
		else:
			return i

def search_right(i,j):
	if j==1:
		if i%2==0:
			return search_right((i-1)//2,1)
		else:
			if seg[i+1]:
				return search_right((i-1)//2,1)
			else:
				return search_right(i+1,0)
	else:
		if i<l//2:
			return search_right(2*i+1+seg[2*i+1],0)
		else:
			return i

ans=0
for i,j in a:
	s=(l//2+1+i)
	p=search_left(s,1)
	q=search_right(s,1)
	ans+=(s-p)*(q-s)*j
	update(s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
a=sorted(list(enumerate(a)),key=lambda x:x[1])
b=[-1,n]
ans=0
for i,j in a:
    c=bisect.bisect(b,i)
    ans+=(i-b[c-1])*(b[c]-i)*j
    bisect.insort(b,i)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
p=[None]*N
for i,a in enumerate(A):
    p[a-1]=i
ans=0
b={-1:1,N:1}
from bisect import bisect
for i in range(N):
    bs=sorted(b.keys())
    s=bisect(bs,p[i])
    ans+=(i+1)*(p[i]-bs[s-1])*(bs[s]-p[i])
    b[p[i]]=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
p=[None]*N
for i,a in enumerate(A):
    p[a-1]=i
ans=0
b=[-1,N]
from bisect import bisect
for i in range(N):
    s=bisect(b,p[i])
    ans+=(i+1)*(p[i]-b[s-1])*(b[s]-p[i])
    b=b[:s]+[p[i]]+b[s:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import random

class Node(object):
    __slots__ = ['value', 'cnt', 'pri', 'lch', 'rch']
    def __init__(self, value):
        self.value = value
        self.cnt = 1
        self.pri = random.randint(1, 1 << 64)
        self.lch = None
        self.rch = None

    def __iter__(self):
        if self.lch is not None:
            for x in self.lch.__iter__():
                yield x
        yield self.value
        if self.rch is not None:
            for x in self.rch.__iter__():
                yield x
    
    def __repr__(self):
        return '{}'.format(self.value)

class Treap(object):
    def __init__(self):
        self.root = None

    def __iter__(self):
        if self.root is None:
            pass
        else:
            for v in self.root:
                yield v
    
    def __repr__(self):
        return "[{}]".format(", ".join(map(str, self)))

    def count(self, node):
        if node is None:
            return 0
        return node.cnt

    def total(self, node):
        if node is None:
            return 0
        return node.ttl

    def update(self, node):
        node.cnt = self.count(node.lch) + self.count(node.rch) + 1

    def merge(self, l, r):
        if l is None:
            return r
        
        if r is None:
            return l
        
        if l.pri  > r.pri:
            l.rch = self.merge(l.rch, r)
            self.update(l)
            return l
        else:
            r.lch = self.merge(l, r.lch)
            self.update(r)
            return r

    def split(self, node, k):
        # print("split:", node, k)
        if node is None:
            return (None, None)
        
        if k <= self.count(node.lch):
            s = self.split(node.lch, k)
            node.lch = s[1]
            self.update(node)
            return (s[0], node)
        else:
            s = self.split(node.rch, k - self.count(node.lch) - 1)
            node.rch = s[0]
            self.update(node)
            return (node, s[1])

    def insert(self, k, v):
        node = Node(v)
        l, r = self.split(self.root, k)
        self.root = self.merge(l, node)
        self.root = self.merge(self.root, r)
    
    def erase(self, k):
        e, r = self.split(self.root, k)
        l, e = self.split(e, k-1)
        self.root = self.merge(l, r)

    def add(self, v):
        k = self.floor_index(v) + 1
        self.insert(k, v)
    
    def remove(self, v):
        k = self.index(v) + 1
        self.erase(k)

    def index(self, value):
        def sub_index(node, k):
            if node is None:
                raise ValueError("{} is not in tree".format(value))
            nv = node.value
            if nv == value:
                return k + self.count(node.lch)
            if nv > value:
                return sub_index(node.lch, k)
            return sub_index(node.rch, k + self.count(node.lch) + 1)
        return sub_index(self.root, 0)

    def __getitem__(self, i):
        def sub_getitem(node, k):
            if node is None:
                raise IndexError("tree index out of range")
            lc = self.count(node.lch)
            if k + lc == i:
                return node.value
            if k + lc > i:
                return sub_getitem(node.lch, k)
            return sub_getitem(node.rch, k + lc + 1)
        return sub_getitem(self.root, 0)

    def floor_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv > value:
            return self.floor_node(node.lch, value, k)
        rf = self.floor_node(node.rch, value, k + self.count(node.lch) + 1)
        if rf[0] is None:
            return (nv, k + self.count(node.lch))
        return rf

    def ceil_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv < value:
            return self.ceil_node(node.rch, value, k + self.count(node.lch))
        lc = self.ceil_node(node.lch, value, k)
        if lc[0] is None:
            return (nv, k + self.count(node.lch))
        return lc
    
    def floor_value(self, node, value):
        if node is None:
            return None

        nv = node.value
        if nv == value:
            return nv
        if nv > value:
            return self.floor_value(node.lch, value)
        rf = self.floor_value(node.rch, value)
        if rf is None:
            return nv
        return rf

    def ceil_value(self, node, value):
        if node is None:
            return None

        nv = node.value
        if nv == value:
            return nv
        if nv < value:
            return self.ceil_value(node.rch, value)
        lc = self.ceil_value(node.lch, value)
        if lc is None:
            return nv
        return lc

    def floor(self, value):
        return self.floor_value(self.root, value)
    
    def ceil(self, value):
        return self.ceil_value(self.root, value)
    
    def floor_index(self, value):
        res = self.floor_node(self.root, value, 0)[1]
        if res is None:
            return -1
        return res
    
    def ceil_index(self, value):
        res = self.ceil_node(self.root, value, 0)[1]
        if res is None:
            return self.count(self.root)
        return res



def solve(N: int, a: "List[int]"):
    sep = Treap()
    sep.add(-1)
    sep.add(N)
    idx = {aa: i for i, aa in enumerate(a)}
    res = 0
    for n in range(1, N+1):
        i = idx[n]
        j = sep.floor(i)
        k = sep.ceil(i)
        res += n * (i - j) * (k - i)
        sep.add(i)
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import random

class Node(object):
    __slots__ = ['value', 'cnt', 'pri', 'lch', 'rch']
    def __init__(self, value):
        self.value = value
        self.cnt = 1
        self.pri = random.randint(1, 1 << 64)
        self.lch = None
        self.rch = None

    def __iter__(self):
        if self.lch is not None:
            for x in self.lch.__iter__():
                yield x
        yield self.value
        if self.rch is not None:
            for x in self.rch.__iter__():
                yield x
    
    def __repr__(self):
        return '{}'.format(self.value)

class Treap(object):
    def __init__(self):
        self.root = None

    def __iter__(self):
        if self.root is None:
            pass
        else:
            for v in self.root:
                yield v
    
    def __repr__(self):
        return "[{}]".format(", ".join(map(str, self)))

    def count(self, node):
        if node is None:
            return 0
        return node.cnt

    def total(self, node):
        if node is None:
            return 0
        return node.ttl

    def update(self, node):
        node.cnt = self.count(node.lch) + self.count(node.rch) + 1

    def merge(self, l, r):
        if l is None:
            return r
        
        if r is None:
            return l
        
        if l.pri  > r.pri:
            l.rch = self.merge(l.rch, r)
            self.update(l)
            return l
        else:
            r.lch = self.merge(l, r.lch)
            self.update(r)
            return r

    def split(self, node, k):
        # print("split:", node, k)
        if node is None:
            return (None, None)
        
        if k <= self.count(node.lch):
            s = self.split(node.lch, k)
            node.lch = s[1]
            self.update(node)
            return (s[0], node)
        else:
            s = self.split(node.rch, k - self.count(node.lch) - 1)
            node.rch = s[0]
            self.update(node)
            return (node, s[1])

    def insert(self, k, v):
        node = Node(v)
        l, r = self.split(self.root, k)
        self.root = self.merge(l, node)
        self.root = self.merge(self.root, r)
    
    def erase(self, k):
        e, r = self.split(self.root, k)
        l, e = self.split(e, k-1)
        self.root = self.merge(l, r)

    def add(self, v):
        k = self.floor_index(v) + 1
        self.insert(k, v)
    
    def remove(self, v):
        k = self.index(v) + 1
        self.erase(k)

    def index(self, value):
        def sub_index(node, k):
            if node is None:
                raise ValueError("{} is not in tree".format(value))
            nv = node.value
            if nv == value:
                return k + self.count(node.lch)
            if nv > value:
                return sub_index(node.lch, k)
            return sub_index(node.rch, k + self.count(node.lch) + 1)
        return sub_index(self.root, 0)

    def __getitem__(self, i):
        def sub_getitem(node, k):
            if node is None:
                raise IndexError("tree index out of range")
            lc = self.count(node.lch)
            if k + lc == i:
                return node.value
            if k + lc > i:
                return sub_getitem(node.lch, k)
            return sub_getitem(node.rch, k + lc + 1)
        return sub_getitem(self.root, 0)

    def floor_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv > value:
            return self.floor_node(node.lch, value, k)
        rf = self.floor_node(node.rch, value, k + self.count(node.lch) + 1)
        if rf[0] is None:
            return (nv, k + self.count(node.lch))
        return rf

    def ceil_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv < value:
            return self.ceil_node(node.rch, value, k + self.count(node.lch))
        lc = self.ceil_node(node.lch, value, k)
        if lc[0] is None:
            return (nv, k + self.count(node.lch))
        return lc
    
    def floor(self, value):
        return self.floor_node(self.root, value, 0)[0]
    
    def ceil(self, value):
        return self.ceil_node(self.root, value, 0)[0]
    
    def floor_index(self, value):
        res = self.floor_node(self.root, value, 0)[1]
        if res is None:
            return -1
        return res
    
    def ceil_index(self, value):
        res = self.ceil_node(self.root, value, 0)[1]
        if res is None:
            return self.count(self.root)
        return res



def solve(N: int, a: "List[int]"):
    sep = Treap()
    sep.add(-1)
    sep.add(N)
    idx = {aa: i for i, aa in enumerate(a)}
    res = 0
    for n in range(1, N+1):
        i = idx[n]
        j = sep.floor(i)
        k = sep.ceil(i)
        res += n * (i - j) * (k - i)
        sep.add(i)
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import random

class Node(object):
    def __init__(self, value):
        self.value = value
        self.cnt = 1
        self.ttl = value
        self.pri = random.randint(1, 1 << 64)
        self.lch = None
        self.rch = None

    def __iter__(self):
        if self.lch is not None:
            for x in self.lch.__iter__():
                yield x
        yield self.value
        if self.rch is not None:
            for x in self.rch.__iter__():
                yield x
    
    def __repr__(self):
        return '{}'.format(self.value)

class Treap(object):
    def __init__(self):
        self.root = None

    def __iter__(self):
        if self.root is None:
            pass
        else:
            for v in self.root:
                yield v
    
    def __repr__(self):
        return "[{}]".format(", ".join(map(str, self)))

    def count(self, node):
        if node is None:
            return 0
        return node.cnt

    def total(self, node):
        if node is None:
            return 0
        return node.ttl

    def update(self, node):
        node.cnt = self.count(node.lch) + self.count(node.rch) + 1
        node.ttl = self.total(node.lch) + self.total(node.rch) + node.value

    def merge(self, l, r):
        if l is None:
            return r
        
        if r is None:
            return l
        
        if l.pri  > r.pri:
            l.rch = self.merge(l.rch, r)
            self.update(l)
            return l
        else:
            r.lch = self.merge(l, r.lch)
            self.update(r)
            return r

    def split(self, node, k):
        # print("split:", node, k)
        if node is None:
            return (None, None)
        
        if k <= self.count(node.lch):
            s = self.split(node.lch, k)
            node.lch = s[1]
            self.update(node)
            return (s[0], node)
        else:
            s = self.split(node.rch, k - self.count(node.lch) - 1)
            node.rch = s[0]
            self.update(node)
            return (node, s[1])

    def insert(self, k, v):
        node = Node(v)
        l, r = self.split(self.root, k)
        self.root = self.merge(l, node)
        self.root = self.merge(self.root, r)
    
    def erase(self, k):
        e, r = self.split(self.root, k)
        l, e = self.split(e, k-1)
        self.root = self.merge(l, r)

    def add(self, v):
        k = self.floor_index(v) + 1
        self.insert(k, v)
    
    def remove(self, v):
        k = self.index(v) + 1
        self.erase(k)

    def index(self, value):
        def sub_index(node, k):
            if node is None:
                raise ValueError("{} is not in tree".format(value))
            nv = node.value
            if nv == value:
                return k + self.count(node.lch)
            if nv > value:
                return sub_index(node.lch, k)
            return sub_index(node.rch, k + self.count(node.lch) + 1)
        return sub_index(self.root, 0)

    def __getitem__(self, i):
        def sub_getitem(node, k):
            if node is None:
                raise IndexError("tree index out of range")
            lc = self.count(node.lch)
            if k + lc == i:
                return node.value
            if k + lc > i:
                return sub_getitem(node.lch, k)
            return sub_getitem(node.rch, k + lc + 1)
        return sub_getitem(self.root, 0)

    def floor_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv > value:
            return self.floor_node(node.lch, value, k)
        rf = self.floor_node(node.rch, value, k + self.count(node.lch) + 1)
        if rf[0] is None:
            return (nv, k + self.count(node.lch))
        return rf

    def ceil_node(self, node, value, k):
        if node is None:
            return (None, None)

        nv = node.value
        if nv == value:
            return (nv, k + self.count(node.lch))
        if nv < value:
            return self.ceil_node(node.rch, value, k + self.count(node.lch))
        lc = self.ceil_node(node.lch, value, k)
        if lc[0] is None:
            return (nv, k + self.count(node.lch))
        return lc
    
    def floor(self, value):
        return self.floor_node(self.root, value, 0)[0]
    
    def ceil(self, value):
        return self.ceil_node(self.root, value, 0)[0]
    
    def floor_index(self, value):
        res = self.floor_node(self.root, value, 0)[1]
        if res is None:
            return -1
        return res
    
    def ceil_index(self, value):
        res = self.ceil_node(self.root, value, 0)[1]
        if res is None:
            return self.count(self.root)
        return res



def solve(N: int, a: "List[int]"):
    sep = Treap()
    sep.add(-1)
    sep.add(N)
    idx = {aa: i for i, aa in enumerate(a)}
    res = 0
    for n in range(1, N+1):
        i = idx[n]
        j = sep.floor(i)
        k = sep.ceil(i)
        res += n * (i - j) * (k - i)
        sep.add(i)
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()