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

Solution code:
#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
 
################################################################
'''
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
 
#b[i]:iが何番目か
b = [None]*(n+1)
for i in range(n):
    b[a[i]] = i
'''
def inpl(): return [int(i) for i in input().split()]
n = int(input())
a = inpl()
b = {a[i]: i for i in xrange(n)}
 
root = Avltree()
ass = 0
 
for i in xrange(1,n+1):
    l = root.search_lower(b[i],None)
    r = root.search_higher(b[i],None)
    if l == None:
        l = -1
    if r == None:
        r = n
    ass += (b[i]-l)*(r-b[i])*i
    root.insert(b[i])
print(ass)

Submission status: Runtime Error

Solution code:
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[0:mini])
    if mini != d-1:
        result += minisum(x[mini+1:d])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

s = 0
for i in range(N):
    l = i
    while l>0:
        if A[l-1] > a[i]:
            l -= 1
        else:
            break
    r = i
    while r<N-1:
        if A[r+1] > a[i]:
            r += 1
        else:
            break
    
    s += A[i] * (i-l+1) * (r-i+1)
    
print(s)

Submission status: Runtime Error

Solution code:
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 0:
        return 0
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[:mini])
    if mini != d-1:
        result += minisum(x[mini+1:])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))

Submission status: Runtime Error

Solution code:
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    result = 0
    if mini != 0:
        result += minisum(x[0:mini])
    if mini != d-1:
        result += minisum(x[mini+1:d])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))

Submission status: Runtime Error

Solution code:
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[0:mini])
    if mini != d-1:
        result += minisum(x[mini+1:d])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))

Submission status: Runtime Error

Solution code:
def min(li):
  min = -1
  for i in li:
    if min > i:
      min = i;
  return min
  

n = int(input())
l = input().split(' ')
sum = 0;

for l in range(n):
  for r in range(l,n):
    sum += min(l[:r])
    
print(sum)

Submission status: Runtime Error

Solution code:
def min(li):
  min = -1
  for i in li:
    if min > i:
      min = i;
  return min
  

n = int(input())
l = input().split(' ')
sum = 0;

for l in range(n):
  for r in range(r,n):
    sum += min(l[:r])
    
print(sum)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    import numpy as np
    A = np.array(A)

    def f(A):
        n = len(A)
        if not n:
            return 0
        if n == 1:
            return A[0]

        i = np.argmin(A)
        return A[i]*(i+1)*(n-i) + f(A[:i]) + f(A[i+1:])

    return f(A)


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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(int(a[k:l+1])))
print(score)

Submission status: Runtime Error

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(int(a[k:l+1]))
print(score)

Submission status: Runtime Error

Solution code:
// 解説pdfの方針に沿った解答
// 参考： http://agc005.contest.atcoder.jp/submissions/904878

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <climits>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

const int N = 1234567;

int pr[N]; // 数列のi番目の数値から左に辿り、最初により小さい数値があるindex
int ne[N]; // 数列のi番目の数値から右に辿り、最初により小さい数値があるindex
int pos[N];  // 数値xがある数列のindexを保持

int main() {
    int N;
    cin >> N;
    FOR(i, 1, N + 1) {
        int a;
        cin >> a;
        pos[a] = i;
    }
    REP(i, N+2) {
        pr[i] = i - 1;
        ne[i] = i + 1;
    }

    long long ans = 0;
    for (int i = N; i >= 1; i--) {
        // j: 数値iがある数列のindex
        int j = pos[i];
        // 数値i * 数値iが最小値となるような部分配列の数
        ans += i * 1LL * (j - pr[j]) * (ne[j] - j);

        // 例えば以下の数列で、今 数値i = 4, j = 5とする。
        //  数列 .. 3 7 8 4 9 2
        //   idx    2 3 4 5 6 7
        //  このとき、pr[5] = 2, ne[5] = 7。
        // 数値4を処理し終わった後は、数値4にとってのne, prを使ってテーブルを更新。
        // この場合、数値3にとってのneは、数値4にとってのneと等しくなる。
        // また、    数値2にとってのprは、数値4にとってのneと等しくなる。
        // 式で書くと ne[2] = ne[7], pr[7] = pr[7]となる。

        pr[ne[j]] = pr[j];
        ne[pr[j]] = ne[j];
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys 
import numpypy as np

N = int(sys.stdin.readline())
P = np.array([int(x) for x in sys.stdin.readline().split()])

SUM = np.sum([np.sum([min(P[l:r+1]) for r in range(l, N)]) for l in range(N)])

print(SUM)