結果

問題 No.833 かっこいい電車
ユーザー simamumusimamumu
提出日時 2019-05-24 23:02:42
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,380 bytes
コンパイル時間 76 ms
コンパイル使用メモリ 11,416 KB
実行使用メモリ 21,888 KB
最終ジャッジ日時 2023-09-14 20:55:27
合計ジャッジ時間 6,744 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 616 ms
21,888 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 34 ms
10,476 KB
testcase_05 AC 33 ms
10,572 KB
testcase_06 AC 34 ms
10,468 KB
testcase_07 WA -
testcase_08 AC 33 ms
10,624 KB
testcase_09 AC 33 ms
10,628 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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:
            ind = bisect.bisect_left(spl,x)
            spl = spl[:ind] + spl[ind+1:]
    elif q == 2:
        ind = bisect.bisect_right(spl,x)
        spl = spl[:ind] + [x] + spl[ind:]
    elif q == 3:
        BIT_add(x,1)
    elif q == 4:
        r = Find(x)
        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))

    #print(spl)

for a in ans:
    print(a)
0