結果

問題 No.1014 competitive fighting
コンテスト
ユーザー tpyneriver
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

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