結果

問題 No.921 ずんだアロー
ユーザー NoneNone
提出日時 2021-03-01 21:10:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 6,252 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 110,848 KB
最終ジャッジ日時 2024-10-03 00:58:38
合計ジャッジ時間 4,009 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,992 KB
testcase_01 AC 41 ms
53,504 KB
testcase_02 AC 41 ms
52,736 KB
testcase_03 AC 40 ms
53,120 KB
testcase_04 AC 40 ms
53,248 KB
testcase_05 AC 40 ms
53,248 KB
testcase_06 AC 58 ms
66,176 KB
testcase_07 AC 47 ms
60,800 KB
testcase_08 AC 41 ms
53,120 KB
testcase_09 AC 41 ms
53,888 KB
testcase_10 AC 188 ms
107,244 KB
testcase_11 AC 195 ms
110,592 KB
testcase_12 AC 109 ms
80,628 KB
testcase_13 AC 169 ms
100,736 KB
testcase_14 AC 173 ms
103,552 KB
testcase_15 AC 138 ms
90,932 KB
testcase_16 AC 96 ms
77,348 KB
testcase_17 AC 179 ms
106,584 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 195 ms
110,848 KB
testcase_24 AC 65 ms
82,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
########## 加算 ############################
# 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(
        """
8
0 1 2 3 4 5 6 7
        """
            .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)


########## min ############################
# 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)
    st[i]+=a0

print(st.get_range(0,N))
0