結果

問題 No.1014 competitive fighting
ユーザー tpynerivertpyneriver
提出日時 2020-03-08 02:39:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,514 ms / 2,000 ms
コード長 3,228 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 86,872 KB
実行使用メモリ 153,760 KB
最終ジャッジ日時 2023-09-21 17:22:53
合計ジャッジ時間 42,278 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
71,468 KB
testcase_01 AC 75 ms
71,600 KB
testcase_02 AC 76 ms
71,492 KB
testcase_03 AC 75 ms
71,348 KB
testcase_04 AC 76 ms
71,368 KB
testcase_05 AC 1,514 ms
139,412 KB
testcase_06 AC 1,102 ms
139,532 KB
testcase_07 AC 1,085 ms
139,500 KB
testcase_08 AC 1,499 ms
139,508 KB
testcase_09 AC 1,484 ms
139,432 KB
testcase_10 AC 504 ms
153,760 KB
testcase_11 AC 375 ms
151,108 KB
testcase_12 AC 1,492 ms
139,716 KB
testcase_13 AC 950 ms
114,752 KB
testcase_14 AC 708 ms
106,196 KB
testcase_15 AC 908 ms
117,392 KB
testcase_16 AC 174 ms
80,396 KB
testcase_17 AC 489 ms
93,080 KB
testcase_18 AC 1,043 ms
132,092 KB
testcase_19 AC 1,482 ms
152,012 KB
testcase_20 AC 643 ms
105,368 KB
testcase_21 AC 1,185 ms
137,764 KB
testcase_22 AC 1,026 ms
116,548 KB
testcase_23 AC 521 ms
94,592 KB
testcase_24 AC 495 ms
95,324 KB
testcase_25 AC 259 ms
82,784 KB
testcase_26 AC 984 ms
137,212 KB
testcase_27 AC 437 ms
90,068 KB
testcase_28 AC 521 ms
92,556 KB
testcase_29 AC 127 ms
77,588 KB
testcase_30 AC 1,088 ms
153,248 KB
testcase_31 AC 944 ms
137,892 KB
testcase_32 AC 120 ms
77,808 KB
testcase_33 AC 206 ms
82,088 KB
testcase_34 AC 618 ms
137,940 KB
testcase_35 AC 769 ms
152,560 KB
testcase_36 AC 578 ms
116,724 KB
testcase_37 AC 154 ms
79,548 KB
testcase_38 AC 577 ms
116,516 KB
testcase_39 AC 382 ms
99,396 KB
testcase_40 AC 548 ms
121,084 KB
testcase_41 AC 401 ms
102,544 KB
testcase_42 AC 684 ms
151,920 KB
testcase_43 AC 178 ms
81,172 KB
testcase_44 AC 719 ms
131,604 KB
testcase_45 AC 497 ms
116,160 KB
testcase_46 AC 192 ms
83,348 KB
testcase_47 AC 362 ms
98,572 KB
testcase_48 AC 609 ms
125,900 KB
testcase_49 AC 171 ms
79,672 KB
testcase_50 AC 744 ms
132,208 KB
testcase_51 AC 430 ms
117,404 KB
testcase_52 AC 160 ms
80,028 KB
testcase_53 AC 1,480 ms
139,592 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)
    
    cnt = valtable.get(cA[pj])
    valtable.update(cA[pj], 0)
    res = max(res, B[pj] + valtable.query(0, right[pj]))
    valtable.update(cA[pj], cnt)
    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