結果
| 問題 |
No.921 ずんだアロー
|
| コンテスト | |
| ユーザー |
 None
|
| 提出日時 | 2021-03-01 21:25:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,315 bytes |
| コンパイル時間 | 323 ms |
| コンパイル使用メモリ | 82,140 KB |
| 実行使用メモリ | 111,200 KB |
| 最終ジャッジ日時 | 2024-10-03 00:59:06 |
| 合計ジャッジ時間 | 3,684 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 WA * 5 |
ソースコード
"""
########## 加算 ############################
# 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
#############################################################
def example():
global input
example = iter(
"""
"""
.strip().split("\n"))
input = lambda: next(example)
#############################################################
import sys
from bisect import *
input = sys.stdin.readline
# example()
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(2,N):
a0=st.get_range(0,i-1)
if st[i]<=1:
st[i]=st[i]+a0
else:
st[i]=max(st[i]+a0,st[i]-1+st[i-1])
print(st.get_range(0,N))