結果

問題 No.1096 Range Sums
ユーザー kusirakusirakusirakusira
提出日時 2024-02-12 00:15:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 174 ms / 2,000 ms
コード長 22,985 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 124,868 KB
最終ジャッジ日時 2024-09-28 17:47:15
合計ジャッジ時間 3,515 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
83,092 KB
testcase_01 AC 124 ms
82,932 KB
testcase_02 AC 124 ms
82,860 KB
testcase_03 AC 122 ms
82,692 KB
testcase_04 AC 118 ms
83,036 KB
testcase_05 AC 118 ms
83,008 KB
testcase_06 AC 118 ms
82,664 KB
testcase_07 AC 118 ms
83,020 KB
testcase_08 AC 120 ms
82,724 KB
testcase_09 AC 120 ms
82,480 KB
testcase_10 AC 167 ms
124,828 KB
testcase_11 AC 161 ms
124,812 KB
testcase_12 AC 174 ms
124,280 KB
testcase_13 AC 168 ms
124,468 KB
testcase_14 AC 167 ms
124,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# Python3/Pypy3
#-------------------------------------------------------------------
from bisect import *
from heapq import *
import collections
from collections import deque
from queue import Queue
from itertools import groupby
import itertools
import math
import array
import string
import copy
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from functools import reduce
from functools import cmp_to_key
from operator import and_, or_, xor
#便---------------------------------------------------------------
INF = 10**20
inf = 10**10
mod = 998244353
MOD = 10**9+7
bigmod = 8128812800000059
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")
#---------------------------------------------------------------------
import sys
sys.setrecursionlimit(10 ** 5 + 10000)
input = sys.stdin.readline ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LIS(): return list(map(int, SI()))
def LA(f): return list(map(f, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return input().strip('\n')
def MS(): return input().split()
def LS(): return list(input().strip('\n'))
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def LMS(rows_number): return [MS() for _ in range(rows_number)]
#------------------------------------------------------------------------
######
def ceil(a,b): #
return (a+b-1)//b
def inv(a,p): #ap(ap)
return pow(a,p-2,p)%p
def removeDuplicates_2D(A): #
return list(map(list, set(map(tuple, A))))
def cumulativeSum_1D(A): #A
return list(itertools.accumulate(A))
def cumulativeSum_2D(S): #S =>
h = len(S)
w = len(S[0])
CS = [[0 for _ in range(w)]for _ in range(h)]
CCS = [[0 for _ in range(w)]for _ in range(h)]
for i in range(h):
for j in range(w):
if(j==0):
CS[i][0] = S[i][0]
else:
CS[i][j] = CS[i][j-1] + S[i][j]
for i in range(h):
for j in range(w):
if(i==0):
CCS[0][j] = CS[0][j]
else:
CCS[i][j] = CCS[i-1][j] + CS[i][j]
return CCS
def string_to_runLength(S: str): #/
grouped = groupby(S)
res = []
for k, v in grouped:
res.append((k, int(len(list(v)))))
return res
def runLength_to_string(L: "list[tuple]"): # =>
res = ""
for c, n in L:
res += c * int(n)
return res
def bfs(i,G): # i:
n = len(G)
dist = [-1] * n
pre = [-1] * n
que = deque()
dist[i] = 0
que.append(i)
while not len(que)==0:
v = que.popleft()
for next_v in G[v]:
if dist[next_v] != -1:
continue
dist[next_v] = dist[v] + 1
pre[next_v] = v
que.append(next_v)
return dist,pre
def bfs01(s, G): # i: => dist
N = len(G)
dist = [INF] * N
S = deque([s])
T = deque()
dist[s] = 0
d = 0
while S:
while S:
v = S.popleft()
for c, w in G[v]:
if d+c < dist[w]:
dist[w] = d+c
if c:
T.append(w)
else:
S.append(w)
S, T = T, S
d += 1
return dist
def dijkstra(s,G): #s: => cost,pre | G:(,)
n = len(G)
hq = [(0, s)]
heapify(hq)
cost = [INF]*n
cost[s]= 0
pre = [-1] * n
while hq:
c,v = heappop(hq)
if c > cost[v]:
continue
for d,u in G[v]:
tmp = d+cost[v]
if tmp < cost[u]:
cost[u] = tmp
pre[u] = v
heappush(hq,(tmp,u))
return cost, pre
def coordinates(A): # ( : ),2(: ),
B = sorted(set(A))
C = { v: i for i, v in enumerate(B) }
D = { i: v for i, v in enumerate(B) }
E = list(map(lambda v: C[v], A))
return C, D, E
def eng_L(): return list(string.ascii_lowercase)
def ENG_L(): return list(string.ascii_uppercase)
def bit_len(n): #bit
return n.bit_length()
def bit_cnt(n): # bit1
cnt = 0
for i in range(bit_len(n)+1):
cnt += n>>i & 1
return cnt
def idx_le(A, x): # x / "No"
return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_lt(A, x): # x / "No"
return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"
def idx_ge(A, x): # x / "No"
return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No"
def idx_gt(A, x): # x / "No"
return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No"
def cnt_le(A, x): # x
if(idx_le(A, x) == "No"): return 0
return idx_le(A, x) + 1
def cnt_lt(A, x): # x
if(idx_lt(A, x) == "No"): return 0
return idx_lt(A, x) + 1
def cnt_ge(A, x): # x
return len(A) - cnt_lt(A, x)
def cnt_gt(A, x): # x
return len(A) - cnt_le(A, x)
######
def transpose(A): #
A_t = []
for i in range(len(A[0])) :
tmp = []
for v in A :
tmp.append(v[i])
A_t.append(tmp)
return A_t
def rotate_matrix(A): #90
return transpose(A[::-1])
def convert(S,c): # | S: c:(ex "#",1)
s = set()
h = len(S)
w = len(S[0])
for i in range(h):
for j in range(w):
if S[i][j] == c:
s.add((i, j))
return s
def normalize(s): # # x y 0
if(len(s)==0): return set()
mi = min(i for (i, j) in s)
mj = min(j for (i, j) in s)
return set((i - mi, j - mj) for (i, j) in s)
def up_shift(S): #
S = S[1:] + [S[0]]
return S
def down_shift(S): #
S = [S[-1]] + S[:-1]
return S
def left_shift(S): #
h = len(S)
w = len(S[0])
nS = [[0 for j in range(len(S[0]))]for i in range(len(S))]
for i in range(h):
for j in range(w):
nS[i][j] = S[i][(j+1)%w]
return nS
def right_shift(S): #
h = len(S)
w = len(S[0])
nS = [[0 for j in range(len(S[0]))]for i in range(len(S))]
for i in range(h):
for j in range(w):
nS[i][j] = S[i][(j-1)%w]
return nS
######
def allAND(A): # AAND
return reduce(and_, A)
def allOR(A): # AOR
return reduce(or_, A)
def allXOR(A): # AXOR
return reduce(xor, A)
def allGCD(A): # AGCD
if(len(A)==1):
return A[0]
g = math.gcd(A[0],A[1])
for i in range(1,len(A)):
g = math.gcd(g, A[i])
return g
def mex(A): #Amex
B = set()
for a in A:
if(a>=0):
B.add(a)
B = list(B)
B.sort()
if(len(B)==0):
return 0
if(B[0]!=0):
return 0
m = 0
for i in range(1,len(B)):
if(B[i]==B[i-1]+1):
m +=1
else:
break
return m +1
def gcd(a,b): #ab
return math.gcd(a,b)
def lcm(a,b): #ab
return a*b//gcd(a,b)
def extgcd(a, b): # a,b =>ax+by=gcd(a,b)(g,x,y) a,bxab
if b:
d, y, x = extgcd(b, a % b)
y -= (a // b)*x
return d, x, y
return a, 1, 0
def fact_L(n,mod): # [0!, 1! ..., n!]
fact = [1]
p = 1
for i in range(1,n+1):
p *= i
p %= mod
fact.append(p)
return fact
def bitCount_L(n): # nbit
bitcount = [0] * (n+1)
for i in range(1,n+1):
bitcount[i] = bitcount[i//2] + i%2
return bitcount
def factorial(n, m=0): #n | m:mod()
if(n<0):
return -1
elif(n==0):
return 1
P = 1
for i in range(1,n+1):
P *= i
if(m==0):
continue
P %= m
return P
def nPr(n, r, m=0): #nPr
if(n<=0 or r<0 or n<r):
return -1
if(r==0):
return 1
P = 1
for i in range(n,n-r,-1):
P *= i
if(m==0):
continue
P %= m
return P
def nCr(n, r, m=0): #nCr
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
N = 1
for i in range(r):
N *= n-i
if(m==0):
continue
N %= m
R = factorial(r)
return N//R
def nCrm(n,r,m=mod): #nCr%mod
if(n<r):
return 0
if(n==r):
return 1
if(n<=0 or r<0 or n<r):
return -1
over=1
for i in range(n-r+1,n+1):
over *= i
over %= m
under=1
for i in range(1,r+1):
under *= i
under %= m
return over*pow(under,m-2,m)%m
def is_prime(n): # => True/False
if n == 2:
return 1
if n == 1 or n%2 == 0:
return 0
m = n - 1
lsb = m & -m
s = lsb.bit_length()-1
d = m // lsb
test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
for a in test_numbers:
if a == n:
continue
x = pow(a,d,n)
r = 0
if x == 1:
continue
while x != m:
x = pow(x,2,n)
r += 1
if x == 1 or r == s:
return 0
return 1
def prime_L(n): #n
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue
for j in range(i * 2, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
def find_prime_factor(n):
if n%2 == 0:
return 2
m = int(n**0.125)+1
for c in range(1,n):
f = lambda a: (pow(a,2,n)+c)%n
y = 0
g = q = r = 1
k = 0
while g == 1:
x = y
while k < 3*r//4:
y = f(y)
k += 1
while k < r and g == 1:
ys = y
for _ in range(min(m, r-k)):
y = f(y)
q = q*abs(x-y)%n
g = math.gcd(q,n)
k += m
k = r
r *= 2
if g == n:
g = 1
y = ys
while g == 1:
y = f(y)
g = math.gcd(abs(x-y),n)
if g == n:
continue
if is_prime(g):
return g
elif is_prime(n//g):
return n//g
else:
return find_prime_factor(g)
def primeFactorization_2L(n): #2n => [[, ], ...]2
if(n<=10**6):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
else:
res = {}
while not is_prime(n) and n > 1:
p = find_prime_factor(n)
s = 0
while n%p == 0:
n //= p
s += 1
res[p] = s
if n > 1:
res[n] = 1
R = []
for r in res:
R.append([r,res[r]])
R.sort()
return R
def divisor_L(n): #n
if(n==1):
return [1]
if(n<=10**6):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
else:
L = primeFactorization_2L(n)
E = [[]for i in range(len(L))]
for i in range(len(L)):
for j in range(L[i][1]+1):
E[i].append(L[i][0]**j)
D = []
for p in list(itertools.product(*E)):
s = 1
for v in p:
s *= v
D.append(s)
D.sort()
return D
def floorsqrt(n): # N => ⌊√N⌋
# only for n <= 10 ** 18
ok = 10 ** 9 + 10
ng = 0
while ok - ng > 1:
t = (ok + ng) // 2
if t * t > n: ok = t
else: ng = t
return ng
def decimal_to_nAry(d, n): #10n(n<=36) |int => str
if(d == 0): return "0"
str_n = []
while d:
if d % n >= 10:
str_n.append(chr(d%n+55))
else:
str_n.append(str(d%n))
d //= n
return "".join(str_n[::-1])
def nAry_to_decimal(S, n): #n10(n<=36) | str => int
num = 0
S = S.upper()
S = list(S)
for i in range(len(S)):
if(("0"<=S[i]<="9")==False):
S[i] = str(ord(S[i]) - 55)
for i in range(1, len(S)+1):
num += int(S[-i]) * pow(n, (i-1))
return num
def roundOff(x,d): # x:, d:(|) => float
return float(Decimal(x).quantize(Decimal(f"1E{d}"), rounding=ROUND_HALF_UP))
######
def dsin(d): #sin
return math.sin(math.radians(d))
def dcos(d): #cos
return math.cos(math.radians(d))
def rotate(x,y,d,cx=0,cy=0): #P(x,y)A(cx,cy) => [x,y]
nx = (x-cx)*dcos(d)-(y-cy)*dsin(d)
ny = (x-cx)*dsin(d)+(y-cy)*dcos(d)
return [nx+cx,ny+cy]
def findAngle(O,A,B): #∠AOB()
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
u = s[0]*t[0]+s[1]*t[1]
l = (s[0]**2+s[1]**2)**(1/2) * (t[0]**2+t[1]**2)**(1/2)
v = u/l
t = math.degrees(math.acos(v))
return t
def outerProduct(Av,Bv): #(=)(a×b)
return Av[0]*Bv[1] - Bv[0]*Av[1]
def CCW(O,A,B): #OAAB
# -1: , 0: , 1:
s = [A[0]-O[0],A[1]-O[1]]
t = [B[0]-O[0],B[1]-O[1]]
op = outerProduct(s,t)
if(op > 0): return 1
if(op < 0): return -1
if(op == 0): return 0
def matrixMultiplication_2D(a,b,m): #(a×b) m:mod
I,J,K,L = len(a),len(b[0]),len(b),len(a[0])
if(L!=K):
return -1
c = [[0] * J for _ in range(I)]
for i in range(I) :
for j in range(J) :
for k in range(K) :
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= m
return c
def matrixExponentiation_2D(x,n,m): # (x^n) m:mod
y = [[0] * len(x) for _ in range(len(x))]
for i in range(len(x)):
y[i][i] = 1
while n > 0:
if n & 1:
y = matrixMultiplication_2D(x,y,m)
x = matrixMultiplication_2D(x,x,m)
n >>= 1
return y
def twoCircles(A,B): # | [x,y(=),r(=)]
# 1 : 2
# 2 : 2
# 3 : 2
# 4 : 2 2
# 5 : 2 2
x1 = A[0]
x2 = B[0]
y1 = A[1]
y2 = B[1]
r1 = A[2]
r2 = B[2]
d = abs((x1-x2)**2 + (y1-y2)**2)
if(abs(r2-r1)**2>d):
return 1
elif(abs(r2-r1)**2==d):
return 2
elif((r1+r2)**2>d):
return 3
elif((r1+r2)**2==d):
return 4
elif((r1+r2)**2<d):
return 5
######
def TS(_str): #/
print('{}: {}'.format(_str, eval(_str)))
def T2d(A): #
for a in A:
print(*a)
def T3d(A): #
for a in A:
T2d(a)
BR()
def BR(): #
print("---")
#----------------------------------------------------------------------
#-----------------------------------------------------------
'''
######
ceil(a,b): #
inv(a,p): #xp | p
removeDuplicates_2D(A): #
cumulativeSum_1D(A) #A
cumulativeSum_2D(S): #S =>
string_to_runLength(S: str) #/ => [(,), ...]
runLength_to_string(L: "list[tuple]") # =>
bfs(i,G) # i: => dist,pre
bfs01(i,G) # i: => dist
dijkstra(s,G): #s: => cost,pre | G:(,)
coordinates(A) # ( : ),2(: ),
eng_L() #
ENG_L() #
bit_len(n): #bit
bit_cnt(n): # bit1
idx_le(A, x) # x / "No"
idx_lt(A, x) # x / "No"
idx_ge(A, x) # x / "No"
idx_gt(A, x) # x / "No"
cnt_le(A, x) # x
cnt_lt(A, x) # x
cnt_ge(A, x) # x
cnt_gt(A, x) # x
######
transpose(A): #
rotate_matrix(A): #90
convert(S, c): # | S: c:(ex "#",1)
normalize(s): # # x y 0
ex) normalize(convert(S,c))
up_shift(S): #
down_shift(S): #
left_shift(S): #
right_shift(S): #
######
allAND(A): # AAND
allOR(A): # AOR
allXOR(A): # AXOR
allGCD(A): # AGCD
mex(A) #Amex
gcd(a,b) #ab
lcm(a,b) #ab
extgcd(a, b): # a,b =>ax+by=gcd(a,b)(g,x,y) a,bxab
fact_L(n,mod): # [0!, 1! ..., n!]
bitCount_L(n): # nbit
factorial(n,m) #n | m:mod()
nPr(n,r,m) #nPr | m:mod()
nCr(n,r,m) #,nCr | m:mod()
nCrm(n,r,m) #nCr%mod
divisor_L(n) #n
is_prime(n) # => True/False
prime_L(n) #n
primeFactorization_2L(n) #2n => [[, ], ...]2
floorsqrt(n): # N => ⌊√N⌋
decimal_to_nAry(num_10,n) #10n(n<=36) |int => str
nAry_to_decimal(num_n,n) #n10(n<=36) | str => int
roundOff(x,d): # x:, d:(|) => float
######
dsin(d): #sin
dcos(d): #cos
rotate(x,y,d,cx,cy): #P(x,y)A(cx,cy)() => [x,y]
findAngle(O,A,B) #∠AOB() | [x,y(=)]
outerProduct(Av,Bv) #(=)(a×b) | [x,y(=)]
CCW(O,A,B) #OAAB
=> -1:, 0:, 1: | [x,y(=)]
matrixMultiplication_2D(a,b,m) #(a×b) m:mod |
matrixExponentiation_2D(x,n m) # (x^n) m:mod |
twoCircles(A,B): # | [x,y(=),r(=)]
=> 1, 2, 3, 4, 5
######
TS(_str) # / => :××
T2d(A): #
T3d(A): #
BR() #
######
|S|<x => "0"*(x-|S|) + S : str(n).zfill(x)
str.upper()
str.lower()
str.capitalize()
:str.title()
str.swapcase()
→ ASCII ord(s)
ASCII chr(x)
ASCIIa
65:A ~ 90:Z
97:a ~ 122:z
######
le:
lt:
ge:
gt:
'''
#PyPy----------------------------------
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
#----------------------------------------------------------------------------
n = II()
A = LI()
CA = cumulativeSum_1D(A)
s = sum(CA)
t = s
ans = 0
for i in range(n):
ans += t
t -= (n-i)*A[i]
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0