結果

問題 No.1014 competitive fighting
ユーザー kasashimataigakasashimataiga
提出日時 2022-03-28 13:53:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,628 ms / 2,000 ms
コード長 6,223 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 470,920 KB
最終ジャッジ日時 2024-04-24 20:11:05
合計ジャッジ時間 47,093 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
54,016 KB
testcase_01 AC 46 ms
54,016 KB
testcase_02 AC 46 ms
54,144 KB
testcase_03 AC 44 ms
54,016 KB
testcase_04 AC 43 ms
53,632 KB
testcase_05 AC 1,628 ms
324,288 KB
testcase_06 AC 1,492 ms
324,288 KB
testcase_07 AC 1,524 ms
324,732 KB
testcase_08 AC 1,559 ms
324,060 KB
testcase_09 AC 1,526 ms
324,496 KB
testcase_10 AC 1,570 ms
470,920 KB
testcase_11 AC 860 ms
264,712 KB
testcase_12 AC 1,494 ms
324,216 KB
testcase_13 AC 828 ms
204,884 KB
testcase_14 AC 796 ms
197,324 KB
testcase_15 AC 839 ms
209,088 KB
testcase_16 AC 224 ms
84,292 KB
testcase_17 AC 478 ms
132,536 KB
testcase_18 AC 1,353 ms
303,064 KB
testcase_19 AC 1,534 ms
329,792 KB
testcase_20 AC 707 ms
186,192 KB
testcase_21 AC 1,284 ms
311,764 KB
testcase_22 AC 955 ms
220,952 KB
testcase_23 AC 544 ms
141,952 KB
testcase_24 AC 544 ms
140,160 KB
testcase_25 AC 299 ms
93,504 KB
testcase_26 AC 1,282 ms
307,660 KB
testcase_27 AC 492 ms
132,460 KB
testcase_28 AC 488 ms
133,524 KB
testcase_29 AC 157 ms
78,720 KB
testcase_30 AC 1,524 ms
328,856 KB
testcase_31 AC 1,347 ms
302,336 KB
testcase_32 AC 154 ms
79,232 KB
testcase_33 AC 197 ms
89,948 KB
testcase_34 AC 854 ms
254,912 KB
testcase_35 AC 937 ms
268,972 KB
testcase_36 AC 799 ms
253,644 KB
testcase_37 AC 176 ms
81,788 KB
testcase_38 AC 590 ms
179,660 KB
testcase_39 AC 345 ms
127,576 KB
testcase_40 AC 563 ms
180,044 KB
testcase_41 AC 520 ms
170,536 KB
testcase_42 AC 943 ms
267,772 KB
testcase_43 AC 196 ms
89,576 KB
testcase_44 AC 898 ms
261,988 KB
testcase_45 AC 572 ms
173,024 KB
testcase_46 AC 242 ms
100,024 KB
testcase_47 AC 355 ms
126,600 KB
testcase_48 AC 920 ms
255,848 KB
testcase_49 AC 195 ms
82,340 KB
testcase_50 AC 1,103 ms
268,368 KB
testcase_51 AC 566 ms
172,964 KB
testcase_52 AC 178 ms
81,952 KB
testcase_53 AC 1,480 ms
324,388 KB
権限があれば一括ダウンロードができます

ソースコード

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