結果
| 問題 | No.921 ずんだアロー |
| ユーザー |
 None
|
| 提出日時 | 2021-03-01 21:26:32 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 229 ms / 2,000 ms |
| コード長 | 6,043 bytes |
| コンパイル時間 | 378 ms |
| コンパイル使用メモリ | 82,316 KB |
| 実行使用メモリ | 111,092 KB |
| 最終ジャッジ日時 | 2024-04-14 03:50:32 |
| 合計ジャッジ時間 | 4,095 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 47 ms
53,492 KB |
| testcase_01 | AC | 46 ms
53,076 KB |
| testcase_02 | AC | 48 ms
53,972 KB |
| testcase_03 | AC | 44 ms
54,296 KB |
| testcase_04 | AC | 42 ms
55,276 KB |
| testcase_05 | AC | 41 ms
54,176 KB |
| testcase_06 | AC | 62 ms
67,444 KB |
| testcase_07 | AC | 46 ms
61,340 KB |
| testcase_08 | AC | 40 ms
53,660 KB |
| testcase_09 | AC | 41 ms
54,228 KB |
| testcase_10 | AC | 215 ms
107,308 KB |
| testcase_11 | AC | 223 ms
111,068 KB |
| testcase_12 | AC | 132 ms
80,076 KB |
| testcase_13 | AC | 214 ms
100,452 KB |
| testcase_14 | AC | 229 ms
103,980 KB |
| testcase_15 | AC | 178 ms
90,916 KB |
| testcase_16 | AC | 116 ms
77,936 KB |
| testcase_17 | AC | 223 ms
106,628 KB |
| testcase_18 | AC | 68 ms
83,428 KB |
| testcase_19 | AC | 69 ms
83,656 KB |
| testcase_20 | AC | 66 ms
84,396 KB |
| testcase_21 | AC | 66 ms
84,280 KB |
| testcase_22 | AC | 69 ms
83,544 KB |
| testcase_23 | AC | 218 ms
111,092 KB |
| testcase_24 | AC | 65 ms
83,768 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))