結果
| 問題 | No.921 ずんだアロー |
| ユーザー |
 None
|
| 提出日時 | 2021-03-01 21:26:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 217 ms / 2,000 ms |
| コード長 | 6,043 bytes |
| コンパイル時間 | 241 ms |
| コンパイル使用メモリ | 82,408 KB |
| 実行使用メモリ | 110,948 KB |
| 最終ジャッジ日時 | 2024-10-03 00:59:10 |
| 合計ジャッジ時間 | 3,571 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
54,804 KB |
| testcase_01 | AC | 41 ms
53,708 KB |
| testcase_02 | AC | 40 ms
54,340 KB |
| testcase_03 | AC | 40 ms
53,620 KB |
| testcase_04 | AC | 41 ms
53,420 KB |
| testcase_05 | AC | 40 ms
53,280 KB |
| testcase_06 | AC | 59 ms
67,220 KB |
| testcase_07 | AC | 47 ms
60,852 KB |
| testcase_08 | AC | 41 ms
54,372 KB |
| testcase_09 | AC | 42 ms
54,356 KB |
| testcase_10 | AC | 205 ms
107,396 KB |
| testcase_11 | AC | 216 ms
110,476 KB |
| testcase_12 | AC | 121 ms
80,692 KB |
| testcase_13 | AC | 184 ms
100,256 KB |
| testcase_14 | AC | 196 ms
103,688 KB |
| testcase_15 | AC | 157 ms
90,936 KB |
| testcase_16 | AC | 103 ms
77,640 KB |
| testcase_17 | AC | 197 ms
106,336 KB |
| testcase_18 | AC | 66 ms
84,020 KB |
| testcase_19 | AC | 66 ms
84,632 KB |
| testcase_20 | AC | 66 ms
84,476 KB |
| testcase_21 | AC | 66 ms
83,512 KB |
| testcase_22 | AC | 66 ms
84,340 KB |
| testcase_23 | AC | 217 ms
110,948 KB |
| testcase_24 | AC | 66 ms
83,852 KB |
ソースコード
"""
########## 加算 ############################
# chain rule of op
def op(x,y):
return x+y
e = 0
st = SegmentTree(N, op, e)
###########################################
########## 代入 ############################
# chain rule of op
def op(x,y):
return x if x != e else y
e = -float("inf")
st = SegmentTree(N, op, e)
###########################################
########## min ############################
# chain rule of op
def op(x,y):
return x if x < y else y
e = -float("inf")
st = SegmentTree(N, op, e)
###########################################
########## gcd ############################
# chain rule of op
def op(x,y):
return gcd(x,y)
e = 0
st = SegmentTree(N, op, e)
###########################################
########## lcm ############################
# chain rule of op
def op(x,y):
return a*b//gcd(x,y)
e = 1
st = SegmentTree(N, op, e)
###########################################
########## 行列積 ############################
# chain rule of op
def op(A,B):
res = [[0]*len(A) for _ in range(len(A[0]))]
for i in range(len(A)):
for j in range(len(A[0])):
res[i][j] = sum( A[i][k]*B[k][j] for k in range(len(A[0])))
return res
e = [[1,0],[0,1]]
st = SegmentTree(N, op, e)
###########################################
"""
class SegmentTree:
def __init__(self, n, op, e):
self.n = n
self.op = op
self.e = e
self.size = 1 << (self.n - 1).bit_length() # st[self.size + i] = array[i]
self.tree = [self.e] * (self.size << 1)
def build(self, array):
"""bulid seg tree from array"""
for i in range(self.n):
self.tree[self.size + i] = array[i]
for i in range(self.size - 1, 0, -1):
self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])
def update(self, i, x):
i += self.size
self.tree[i] = x
while i > 1:
i >>= 1
self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])
def get_range(self, l, r):
"""
get value from [l, r) (0-indexed)
"""
l += self.size
r += self.size
res_l = self.e
res_r = self.e
while l < r:
if l & 1:
res_l = self.op(res_l, self.tree[l])
l += 1
if r & 1:
r -= 1
res_r = self.op(self.tree[r], res_r)
l >>= 1
r >>= 1
return self.op(res_l, res_r)
def max_right(self,l,func):
"""
return r such that
・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
"""
if l == self.n: return self.n
l += self.size
sm = self.e
while True:
while l % 2 == 0: l >>= 1
if not func(self.op(sm,self.tree[l])):
while l < self.size:
l = 2 * l
if func(self.op(sm,self.tree[l])):
sm = self.op(sm, self.tree[l])
l += 1
return l - self.size
sm = self.op(sm, self.tree[l])
l += 1
if (l & -l) == l: break
return self.n
def min_left(self,r,func):
"""
return l such that
・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
"""
if r == 0: return 0
r += self.size
sm = self.e
while True:
r -= 1
while r > 1 and (r % 2): r >>= 1
if not func(self.op(self.tree[r],sm)):
while r < self.size:
r = 2 * r + 1
if func(self.op(self.tree[r],sm)):
sm = self.op(self.tree[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.tree[r], sm)
if (r & -r) == r: break
return 0
def __getitem__(self, i):
if i<0: i=self.n+i
return self.get_range(i,i+1)
def __setitem__(self, i, value):
if i<0: i=self.n+i
self.update(i,value)
def __iter__(self):
for a in self.tree[self.size:self.size+self.n]:
yield a
def __str__(self):
return str(self.tree[self.size:self.size+self.n])
class CompressSegment:
"""
data = [(x0,A0),(x1,A1),(x2,A2),...]
CS=CompressSegment(data)
range: return compressed coordinate
[xi,xj) -> [i, j)
getitem[i]: return A[xi]
i -> A[xi]
"""
def __init__(self,data):
data.sort(key=lambda x:x[0])
self.X, self.A, self.Xc = [], [], dict()
for i, (x,a) in enumerate(data):
self.X.append(x)
self.A.append(a)
self.Xc[x]=i
def __call__(self, l, r):
return bisect_left(self.X,l), bisect_left(self.X,r)
def range(self, l, r):
return bisect_left(self.X,l), bisect_left(self.X,r)
def __getitem__(self, i):
return self.A[i]
def __iter__(self):
for a in self.A:
yield a
def deg(A):
"""
連続して続く文字を圧縮する（※Counterではない）
[1,1,1,2,2,2,3] -> [(1,3),(2,3),(3,1)]
"""
res=[]
a0, cnt=A[0], 1
for a in A[1:]+[None]:
if a!=a0: res.append((a0,cnt)); cnt=1
else: cnt+=1
a0=a
return res
import sys
from bisect import *
input = sys.stdin.readline
N=int(input())
A=list(map(int, input().split()))
data=deg(A)
N=len(data)
C=[]
for a,cnt in data:
C.append(cnt)
########## max ############################
# chain rule of op
def op(x,y):
return x if x > y else y
e = -float("inf")
st = SegmentTree(N, op, e)
###########################################
st.build(C)
for i in range(1,N):
a0=st.get_range(0,i-1)
if st[i]<=1 and i>=2:
st[i]=st[i]+a0
else:
st[i]=max(st[i]+a0,st[i]-1+st[i-1])
print(st.get_range(0,N))