結果

問題 No.335 門松宝くじ
コンテスト
ユーザー titia
提出日時 2026-07-23 03:46:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,439 ms / 2,000 ms
+ 2µs
コード長 3,880 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 627 ms
コンパイル使用メモリ 95,848 KB
実行使用メモリ 100,372 KB
最終ジャッジ日時 2026-07-23 03:46:47
合計ジャッジ時間 12,105 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,M=list(map(int,input().split()))

ANS=-1
IND=-1

for test in range(M):
    A=list(map(int,input().split()))
    A_INV=[0]*(N+1)

    for i in range(N):
        A_INV[A[i]]=i

    score=0

    
    def seg_function(x,y): # Segment treeで扱うfunction
        return max(x,y)

    seg_el=1<<((N+5).bit_length()) # Segment treeの台の要素数
    SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

    for i in range(N): # Aを対応する箇所へupdate
        SEG[i+seg_el]=A[i]

    for i in range(seg_el-1,0,-1): # 親の部分もupdate
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

    def update(n,x,seg_el): # A[n]をxへ更新
        i=n+seg_el
        SEG[i]=x
        i>>=1 # 子ノードへ
        
        while i!=0:
            SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
            i>>=1
            
    def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
        L=l+seg_el
        R=r+seg_el
        ANS1=0
        ANS2=0

        while L<R:
            if L & 1:
                ANS1=seg_function(ANS1, SEG[L])
                L+=1

            if R & 1:
                R-=1
                ANS2=seg_function(SEG[R], ANS2)
            L>>=1
            R>>=1

        return seg_function(ANS1, ANS2)


    SEG2=[1<<30]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

    for i in range(N): # Aを対応する箇所へupdate. Aは0-indexedなことに注意. 
        SEG2[i+seg_el]=A[i]

    for i in range(seg_el-1,0,-1): # 親の部分もupdate
        SEG2[i]=min(SEG2[i*2],SEG2[i*2+1])

    def update2(n,x,seg_el): # A[n]をxへ更新
        i=n+seg_el
        SEG2[i]=x
        i>>=1 # 子ノードへ
        
        while i!=0:
            SEG2[i]=min(SEG2[i*2],SEG2[i*2+1])
            i>>=1
            
    def getvalues2(l,r): # 区間[l,r)に関するminを調べる
        L=l+seg_el
        R=r+seg_el
        ANS=1<<30

        while L<R:
            if L & 1:
                ANS=min(ANS , SEG2[L])
                L+=1

            if R & 1:
                R-=1
                ANS=min(ANS , SEG2[R])
            L>>=1
            R>>=1

        return ANS

    score=0

    for j in range(1,N+1):
        for k in range(j+1,N+1):
            x=A_INV[j]
            y=A_INV[k]

            score2=0

            if x<y:
                mm=getvalues(0,x)
                if 1<=mm<=N and mm>j:
                    score2=max(score2,k,mm)

                mm=getvalues(x+1,y)
                if 1<=mm<=N and (mm<j or mm>k):
                    score2=max(score2,k,mm)

                mm2=getvalues2(x+1,y)
                #print("!!",mm2)
                if 1<=mm2<=N and (mm2<j or mm2>k):
                    score2=max(score2,k,mm2)
              

                mm=getvalues2(y,N)

                if 1<=mm<=N and mm<k:
                    score2=max(score2,k)
            else:
                #print("!!!!!",j,k)
                mm=getvalues(x+1,N)
                #print("!",mm)
                if 1<=mm<=N and mm>j:
                    score2=max(score2,k,mm)
                    
                mm=getvalues(y+1,x)
                #print("!!",mm)
                if 1<=mm<=N and (mm<j or mm>k):
                    score2=max(score2,k,mm)


                mm2=getvalues2(y+1,x)
                #print("!!",mm2)
                if 1<=mm2<=N and (mm2<j or mm2>k):
                    score2=max(score2,k,mm2)
                    
                mm=getvalues2(0,y)
                #print("!!!",mm)
                if 1<=mm<=N and mm<k:
                    score2=max(score2,k)

            #print(j,k,score2)

            score+=score2

    #print(score)

    if ANS<score:
        ANS=score
        ind=test

print(ind)
0