結果

問題 No.2036 Max Middle
ユーザー 👑 Kazun
提出日時 2022-08-12 22:43:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 3,859 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 110,400 KB
最終ジャッジ日時 2024-09-23 03:23:02
合計ジャッジ時間 2,927 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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

class Binary_Indexed_Tree():
    def __init__(self, L, calc, unit, inv, index=1):
        """ calc を演算とする N 項の Binary Indexed Tree を作成
        calc: 演算 (2変数関数, 可換群)
        unit: 群 calc の単位元 (x+e=e+x=xを満たすe)
        inv : 群 calc の逆元 (1変数関数, x+inv(x)=inv(x)+x=e をみたす inv(x))
        """
        self.calc=calc
        self.unit=unit
        self.inv=inv
        self.index=index
        N=len(L)
        d=max(1,(N-1).bit_length())
        k=2**d
        X=[None]+[unit]*k
        self.num=k
        self.depth=d
        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    X[p]=self.calc(X[p],L[i])
                    p+=p&(-p)
        self.data=X
    def index_number(self, k, index=1):
        """ 第 k 要素の値を出力する.
        k    : 数列の要素
        index: 先頭の要素の番号
        """
        return self.sum(k,k,index)
    def add(self, k, x, index=1):
        """ 第 k 要素に x を加え, 更新を行う.
        k    : 数列の要素
        x    : 加える値
        index: 先頭の要素の番号
        """
        data=self.data; calc=self.calc
        p=k+(1-index)
        while p<=self.num:
            data[p]=calc(self.data[p],x)
            p+=p&(-p)
    def update(self, k, x, index=1):
        """ 第 k 要素を x に変え, 更新を行う.
        k: 数列の要素
        x: 更新後の値
        """
        a=self.index_number(k,index)
        y=self.calc(self.inv(a),x)
        self.add(k,y,index)
    def sum(self, From, To, index=1):
        """ 第 From 要素から第 To 要素までの総和を求める.
        ※From!=1を使うならば, 群でなくてはならない.
        From : 始まり
        To   : 終わり
        index: 先頭の要素の番号
        """
        alpha=max(1,From+(1-index))
        beta=min(self.num,To+(1-index))
        if alpha>beta:
            return self.unit
        elif alpha==1:
            return self.__section(beta)
        else:
            return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))
    def __section(self,x):
        """ B[1]+...+B[x] を求める. """
        data=self.data; calc=self.calc
        S=self.unit
        while x>0:
            S=calc(data[x],S)
            x-=x&(-x)
        return S
    def all_sum(self):
        return self.data[-1]
    def binary_search(self, cond, index=1):
        """ cond(B[1]+...+B[k]) を満たす最小の k を返す.
        cond: 単調増加
        ※ cond(unit)=True の場合の返り値は index-1
        ※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index
        """
        if cond(self.unit):
            return index-1
        j=0
        r=self.num
        t=r
        data=self.data; calc=self.calc
        alpha=self.unit
        for _ in range(self.depth+1):
            if j+t<=self.num:
                beta=calc(alpha,data[j+t])
                if not cond(beta):
                    alpha=beta
                    j+=t
            t>>=1
        return j+index
    def __getitem__(self,index):
        if isinstance(index,int):
            return self.index_number(index,self.index)
        else:
            return [self.index_number(t,self.index) for t in index]
    def __setitem__(self,index,val):
        self.update(index,val,self.index)
#==================================================
N=int(input())
A=list(map(int,input().split()))
S=[0]*N
up=0; down=0
for i in range(1,N):
    if A[i-1]<A[i]:
        S[i]=S[i-1]+1
        up+=1
    else:
        S[i]=S[i-1]-1
        down+=1
T=[0]*N
for i in range(1,N):
    if down:
        T[i]=T[i-1]-1
        down-=1
    else:
        T[i]=T[i-1]+1
print((sum(S)-sum(T))//2)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0