結果

問題 No.1014 competitive fighting
ユーザー tpynerivertpyneriver
提出日時 2020-03-08 02:44:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,223 ms / 2,000 ms
コード長 3,427 bytes
コンパイル時間 794 ms
コンパイル使用メモリ 82,804 KB
実行使用メモリ 153,724 KB
最終ジャッジ日時 2024-07-07 12:49:29
合計ジャッジ時間 27,728 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,120 KB
testcase_01 AC 33 ms
53,576 KB
testcase_02 AC 36 ms
53,376 KB
testcase_03 AC 36 ms
53,248 KB
testcase_04 AC 35 ms
53,376 KB
testcase_05 AC 860 ms
152,948 KB
testcase_06 AC 860 ms
152,828 KB
testcase_07 AC 854 ms
153,580 KB
testcase_08 AC 1,079 ms
153,588 KB
testcase_09 AC 1,223 ms
153,592 KB
testcase_10 AC 459 ms
141,400 KB
testcase_11 AC 270 ms
148,640 KB
testcase_12 AC 1,081 ms
153,208 KB
testcase_13 AC 593 ms
107,528 KB
testcase_14 AC 522 ms
107,264 KB
testcase_15 AC 622 ms
109,916 KB
testcase_16 AC 127 ms
78,800 KB
testcase_17 AC 351 ms
91,952 KB
testcase_18 AC 779 ms
137,856 KB
testcase_19 AC 1,145 ms
152,560 KB
testcase_20 AC 429 ms
103,168 KB
testcase_21 AC 670 ms
129,044 KB
testcase_22 AC 722 ms
123,392 KB
testcase_23 AC 362 ms
92,264 KB
testcase_24 AC 366 ms
92,288 KB
testcase_25 AC 187 ms
80,780 KB
testcase_26 AC 728 ms
127,488 KB
testcase_27 AC 311 ms
89,924 KB
testcase_28 AC 380 ms
91,040 KB
testcase_29 AC 102 ms
76,416 KB
testcase_30 AC 841 ms
152,964 KB
testcase_31 AC 738 ms
138,212 KB
testcase_32 AC 88 ms
76,416 KB
testcase_33 AC 125 ms
79,872 KB
testcase_34 AC 422 ms
127,456 KB
testcase_35 AC 537 ms
152,756 KB
testcase_36 AC 376 ms
119,680 KB
testcase_37 AC 102 ms
77,816 KB
testcase_38 AC 352 ms
123,136 KB
testcase_39 AC 240 ms
96,000 KB
testcase_40 AC 357 ms
122,112 KB
testcase_41 AC 275 ms
109,440 KB
testcase_42 AC 481 ms
134,460 KB
testcase_43 AC 114 ms
79,360 KB
testcase_44 AC 455 ms
132,096 KB
testcase_45 AC 325 ms
108,972 KB
testcase_46 AC 126 ms
81,528 KB
testcase_47 AC 221 ms
93,416 KB
testcase_48 AC 410 ms
119,040 KB
testcase_49 AC 114 ms
78,624 KB
testcase_50 AC 473 ms
132,480 KB
testcase_51 AC 291 ms
110,660 KB
testcase_52 AC 106 ms
78,208 KB
testcase_53 AC 1,098 ms
153,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.buffer.readline
from operator import itemgetter

def compress(L):
    N = len(L)
    L2 = sorted([N*L[i]+i for i in range(N)])
    C = {v : k for k, v in enumerate(L2)}
    return [C[N*L[i]+i] for i in range(N)]

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    def get(self, x):
        return self.data[self.N0+x]  

INF = 10**18

N = int(readline())
ABC = [tuple(map(int, readline().split())) for _ in range(N)]
IdxABD = [(i, a, b, b-c) for i, (a, b, c) in enumerate(ABC)]
IdxABD.sort(key = itemgetter(3))
Idx, A, B, D = map(list, zip(*IdxABD))


cA = compress(A)
sA = sorted(A)
aord = [None]*N
for j in range(N):
    aord[cA[j]] = j


left = [None]*N
for j in range(N):
    ng = -1
    ok = N
    aj = A[j]
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if D[med] >= aj:
            ok = med
        else:
            ng = med
    left[j] = ok
right = [None]*N
for j in range(N):
    ok = -1
    ng = N
    dj = D[j]
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if sA[med] <= dj:
            ok = med
        else:
            ng = med
    right[j] = ng


atable = Segtree(A, INF, initialize = True, segf = min)
valtable = Segtree([0]*N, 0, initialize = False, segf = max)
vt = [0]*N
Ans = [None]*N
ans = [None]*N
seen = 0
maxval = 0
for j in range(N):
    pj = aord[j]
    ansidx = Idx[pj]
    
    if left[pj] <= pj:
        atable.update(pj, INF)
        mina = atable.query(left[pj], N)
        atable.update(pj, A[pj])
    else:
        mina = atable.query(left[pj], N)
    
    res = B[pj]
    if mina <= D[pj]:
        res = INF
    
    inval = False
    for k in range(seen, left[pj]):
        if k == pj:
            inval = True 
            continue
        elif cA[k] < j:
            valtable.update(cA[k], ans[k])
        else:
            valtable.update(cA[k], B[k] + maxval)
    
    if cA[pj] < right[pj]:
        cnt = valtable.get(cA[pj])
        valtable.update(cA[pj], 0)
        res = max(res, B[pj] + valtable.query(0, right[pj]))
        if inval:
            valtable.update(cA[pj], res)
        else:
            valtable.update(cA[pj], cnt)
    else:
        res = max(res, B[pj] + valtable.query(0, right[pj]))
        if inval:
            valtable.update(cA[pj], res)
    
    
    maxval = max(maxval, res)
    ans[pj] = res
    seen = left[pj]
    if res >= INF:
        Ans[ansidx] = 'BAN'
    else:
        Ans[ansidx] = str(res)

print('\n'.join(Ans))
0