結果

問題 No.1170 Never Want to Walk
ユーザー Risu_BasquiatRisu_Basquiat
提出日時 2020-08-14 22:49:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 761 ms / 2,000 ms
コード長 4,317 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 156,732 KB
最終ジャッジ日時 2024-04-18 22:39:50
合計ジャッジ時間 14,705 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 116 ms
83,928 KB
testcase_01 AC 116 ms
84,120 KB
testcase_02 AC 121 ms
84,296 KB
testcase_03 AC 119 ms
84,224 KB
testcase_04 AC 118 ms
84,048 KB
testcase_05 AC 120 ms
84,140 KB
testcase_06 AC 118 ms
84,228 KB
testcase_07 AC 126 ms
84,256 KB
testcase_08 AC 122 ms
84,240 KB
testcase_09 AC 118 ms
84,220 KB
testcase_10 AC 122 ms
84,208 KB
testcase_11 AC 124 ms
84,200 KB
testcase_12 AC 161 ms
89,068 KB
testcase_13 AC 162 ms
89,812 KB
testcase_14 AC 154 ms
89,620 KB
testcase_15 AC 166 ms
89,552 KB
testcase_16 AC 173 ms
89,728 KB
testcase_17 AC 166 ms
89,832 KB
testcase_18 AC 152 ms
89,348 KB
testcase_19 AC 167 ms
89,616 KB
testcase_20 AC 165 ms
89,660 KB
testcase_21 AC 176 ms
89,616 KB
testcase_22 AC 168 ms
89,724 KB
testcase_23 AC 173 ms
89,600 KB
testcase_24 AC 170 ms
89,856 KB
testcase_25 AC 164 ms
89,760 KB
testcase_26 AC 166 ms
89,852 KB
testcase_27 AC 669 ms
150,976 KB
testcase_28 AC 684 ms
153,376 KB
testcase_29 AC 666 ms
152,632 KB
testcase_30 AC 750 ms
151,636 KB
testcase_31 AC 711 ms
150,748 KB
testcase_32 AC 660 ms
149,584 KB
testcase_33 AC 658 ms
150,884 KB
testcase_34 AC 712 ms
155,232 KB
testcase_35 AC 761 ms
152,880 KB
testcase_36 AC 696 ms
150,756 KB
testcase_37 AC 655 ms
150,816 KB
testcase_38 AC 653 ms
156,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f
class unionfind:#早いunionfind,class[i]のように要素指定すると親を得ることができる
    def __init__(self, elements=None):#elementsで初期化
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        # check for previously unknown i
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
        for ancestor in path:#縮約
            self.parents[ancestor] = root
        return root

    def __iter__(self):#for parent in Class:
        return iter(self.parents)

    def union(self, *objects):#オブジェクトをすべて結合
        roots = [self[x] for x in objects]
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, a,b = map(int, input().split())
    X = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    uf=unionfind(list(range(N)))
    pr=-100
    pl=-100
    for i,x in enumerate(X):
        l=bisect_left(X,x+a)
        r=bisect_right(X,x+b)
        if l==N:
            break
        ml=l
        if pr>l:
            uf.union(i,i-1)
            ml=pr
        
        for j in range(ml,r):
            uf.union(i,j)
        pr=r
        pl=l
    for i in range(N):
        print(uf.weights[uf[i]])


if __name__ == "__main__":
    main()
0