結果

問題 No.833 かっこいい電車
コンテスト
ユーザー simamumu
提出日時 2019-05-24 22:30:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,264 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 30,956 KB
最終ジャッジ日時 2024-07-02 03:43:43
合計ジャッジ時間 5,908 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 5 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())



def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
        MIN[x] = min(MIN[x],MIN[y])
        MAX[x] = max(MAX[x],MAX[y])
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1
        MIN[y] = min(MIN[x],MIN[y])
        MAX[y] = max(MAX[x],MAX[y])

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]



def BIT_add(a,w):
    global bit
    x = a
    while x <= N:
        bit[x] += w
        x += x & -x

def BIT_sum(a):
    global bit
    tmp = 0
    x = a
    while x > 0:
        tmp += bit[x]
        x -= x & -x
    return tmp


N,Q = inpl()
aa = inpl()
tmp = 0


bit = [0]*(N+1)
table = [i for i in range(N+1)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N+1)]    #木の長さ
size  = [1 for i in range(N+1)]    #集合のサイズ
MIN = [i for i in range(N+1)]
MAX = [i for i in range(N+1)]

spl = [-1,INF]
ans = []


for i,a in enumerate(aa):
    BIT_add(i+1,a)

for _ in range(Q):
    q,x = inpl()
    if q == 1:
        Unite(x,x+1)
        #if x in spl:
        #    spl.remove(x)
    elif q == 2:
        spl.append(x)
    elif q == 3:
        BIT_add(x,1)
    elif q == 4:
        r = Find(x)
        spl.sort()
        splind = bisect.bisect_left(spl,x)
        right = min(MAX[r],spl[splind])
        left = max(MIN[r],spl[splind-1]+1)
        #print('aaa',left,right,splind,spl)
        ans.append(BIT_sum(right) - BIT_sum(left-1))


for a in ans:
    print(a)
0