結果

問題 No.1014 competitive fighting
コンテスト
ユーザー kasashimataiga
提出日時 2022-03-28 13:53:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,639 ms / 2,000 ms
コード長 6,223 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 470,784 KB
最終ジャッジ日時 2024-11-07 05:04:17
合計ジャッジ時間 48,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 


########################################
from heapq import heappush, heappop
def dijkstra( G, s, INF=10 ** 18):
    """
    https://tjkendev.github.io/procon-library/python/graph/dijkstra.html
    O((|E|+|V|)log|V|)
    V: 頂点数
    G[v] = [(nod, cost)]:
        頂点vから遷移可能な頂点(nod)とそのコスト(cost)
    s: 始点の頂点"""

    N=len(G)
    N+=1
    dist = [INF] * N
    hp = [(0, s)]  # (c, v)
    dist[s] = 0
    while hp:
        c, v = heappop(hp)  #vまで行くコストがc
        if dist[v] < c:
            continue
        for u, cost in G[v]:
            if dist[v] + cost < dist[u]:
                dist[u] = dist[v] + cost
                heappush(hp, (dist[u], u))
    return dist
##################################################



############################################

class range_egde_graph():

    def __init__(self,n):
        self.num = 1 << (n - 1).bit_length()
        self.root=[[] for i in range(3*self.num)]

        for i in range(1,self.num):
            self.root[i].append((2*i,0))
            self.root[i].append((2*i+1,0))
        for i in range(self.num,2*self.num):
            self.root[i].append((i//2+2*self.num-1,0))
        for i in range(1,self.num//2):
            self.root[2*i+2*self.num-1].append((i+2*self.num-1,0))
            self.root[2 * i+1 + 2 * self.num - 1].append((i + 2 * self.num - 1, 0))


    def add(self,l_frm,r_frm,l_to,r_to,cost):
        # [l_frm,r_frm)->[l_to,r_to) にcostの辺をはる
        ind=len(self.root)
        self.root.append([])
        l_to += self.num
        r_to += self.num
        while (l_to < r_to):
            if (l_to & 1):
                self.root[ind].append((l_to,0))

                l_to += 1
            if (r_to & 1):
                self.root[ind].append((r_to-1,0))
                r_to -= 1
            l_to >>= 1
            r_to >>= 1


        l_frm += self.num
        r_frm += self.num
        potens=0
        while (l_frm < r_frm):
            if (l_frm & 1):
                if l_frm<self.num:
                    potens=2*self.num-1
                else:
                    potens=0
                self.root[l_frm+potens].append((ind, cost))

                l_frm += 1
            if (r_frm & 1):
                if l_frm<self.num:
                    potens=2*self.num-1
                else:
                    potens=0
                self.root[r_frm-1+potens].append((ind, cost))
                r_frm -= 1
            l_frm >>= 1
            r_frm >>= 1

    def dijkstra(self,s):
        self.dist= dijkstra(self.root,s+self.num)
        self.res=[10**18]*self.num
        for i in range(self.num):
            self.res[i]=self.dist[i+self.num]
        return self.res

#####################################################


####二分探索###################################

#配列は昇順にソートずみ
def bilower(a,x):
    # a[i]<=x となる最大のiを返す ない時は-1
    if len(a)==0:return -1
    mi=0
    ma=len(a)-1
    if a[0]>x:return -1
    if a[ma]<=x:return ma
    while ma-mi>1:
        mid=(ma+mi)//2
        if a[mid]<=x:mi=mid
        else:ma=mid
    return mi

def bihigher(a,x):
    # a[i]>=x となる最小のiを返す ない時は len(a)
    if len(a)==0:return 0
    mi=0
    ma=len(a)-1
    if a[ma]<x:return ma+1
    if a[0]>=x:return 0
    while ma-mi>1:
        mid=(ma+mi)//2
        if a[mid]>=x:ma=mid
        else:mi=mid
    return ma

def birange(a,l,r):
    #l<=a[i]<=r となるiの個数を返す
    left=bihigher(a,l)
    right=bilower(a,r)
    return right-left+1

################################################


def scc(N,edges):
    M=len(edges)
    start=[0]*(N+1)
    elist=[0]*M
    for e in edges:
        start[e[0]+1]+=1
    for i in range(1,N+1):
        start[i]+=start[i-1]
    counter=start[:]
    for e in edges:
        elist[counter[e[0]]]=e[1]
        counter[e[0]]+=1
    visited=[]
    low=[0]*N
    Ord=[-1]*N
    ids=[0]*N
    NG=[0,0]
    def dfs(v):
        stack=[(v,-1,0),(v,-1,1)]
        while stack:
            v,bef,t=stack.pop()
            if t:
                if bef!=-1 and Ord[v]!=-1:
                    low[bef]=min(low[bef],Ord[v])
                    stack.pop()
                    continue
                low[v]=NG[0]
                Ord[v]=NG[0]
                NG[0]+=1
                visited.append(v)
                for i in range(start[v],start[v+1]):
                    to=elist[i]
                    if Ord[to]==-1:
                        stack.append((to,v,0))
                        stack.append((to,v,1))
                    else:
                        low[v]=min(low[v],Ord[to])
            else:
                if low[v]==Ord[v]:
                    while(True):
                        u=visited.pop()
                        Ord[u]=N
                        ids[u]=NG[1]
                        if u==v:
                            break
                    NG[1]+=1
                low[bef]=min(low[bef],low[v])
    for i in range(N):
        if Ord[i]==-1:
            dfs(i)
    for i in range(N):
        ids[i]=NG[1]-1-ids[i]
    group_num=NG[1]
    counts=[0]*group_num
    for x in ids:
        counts[x]+=1
    groups=[[] for i in range(group_num)]
    for i in range(N):
        groups[ids[i]].append(i)
    return groups



n=int(input())
e=[]
for i in range(n):
    a,b,c=map(int,input().split())
    e.append((a,b,c,i))

p=[0]*n
e.sort(key=lambda x:x[0])
a=[]
b=[]
c=[]
for x,y,z,i in e:
    p[i]=len(a)
    a.append(x)
    b.append(y)
    c.append(z)

g=range_egde_graph(n)
edge=[]


for i in range(n):
    ind=bilower(a,b[i]-c[i])
    if not (0<=i<=ind):g.add(i,i+1,0,ind+1,b[i])
    else:
        g.add(i, i + 1, 0, i, b[i])
        g.add(i,i+1,i+1,ind+1,b[i])

for i in range(len(g.root)):
    for j,cost in g.root[i]:edge.append((i,j))



s=scc(len(g.root),edge)

s.reverse()
dp=[0]*(len(g.root))

for i in range(len(s)):
    for nod in s[i]:
        if 0<=nod-g.num<len(b):
            dp[nod]=b[nod-g.num]
        if len(s[i])>=2:dp[nod]=10**18
        for to,cost in g.root[nod]:
            dp[nod]=max(dp[nod],dp[to]+cost)

for i in range(n):
    res=dp[p[i]+g.num]
    if res>=10**18:res="BAN"
    print(res)
0