結果

問題 No.33 アメーバがたくさん
ユーザー ciel
提出日時 2014-11-28 15:24:42
言語 Python3
(3.7.1 + numpy 1.14.5 + scipy 1.1.0)
結果
AC  
実行時間 33 ms
コード長 1,152 Byte
コンパイル時間 62 ms
使用メモリ 5,832 KB
最終ジャッジ日時 2019-04-20 03:50:28

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 33 ms
5,832 KB
2.txt AC 30 ms
5,832 KB
3.txt AC 29 ms
5,828 KB
4.txt AC 30 ms
5,832 KB
5.txt AC 32 ms
5,832 KB
6.txt AC 31 ms
5,828 KB
7.txt AC 31 ms
5,828 KB
8.txt AC 29 ms
5,832 KB
9.txt AC 31 ms
5,832 KB
10.txt AC 30 ms
5,832 KB
99_challenge01.txt AC 31 ms
5,832 KB
テストケース一括ダウンロード

ソースコード

diff #
#!/usr/bin/python
#coding:utf-8
#derived from checkio painting-wall (presented by me)
#http://www.checkio.org/mission/painting-wall/share/8a0e0061de3ff95664776d904d309e57/
import bisect

def checkio(data):
	ret_idx=0
	result=0
	se=[]
	for l,r in data:
		ret_idx+=1
		right_idx=bisect.bisect_left(se,(l,0)) #l <= se[right_idx][0]
		if right_idx!=0:
			left_idx=right_idx-1
			if l<=se[left_idx][1]: # overlap with left
				l=se[left_idx][0]
				r=max(r,se[left_idx][1])
				result-=se[left_idx][1]-se[left_idx][0]+1
				se.pop(left_idx)
				right_idx-=1
		while right_idx<len(se) and se[right_idx][0]<=r: # overlap with right
			r=max(r,se[right_idx][1])
			result-=se[right_idx][1]-se[right_idx][0]+1
			se.pop(right_idx)
		result+=r-l+1
		se.insert(right_idx,(l,r))
	return result

if __name__ == '__main__':
	from collections import defaultdict
	import sys
	if sys.version_info[0]>=3: raw_input=input
	dic=defaultdict(list)
	n,d,t=[int(e) for e in raw_input().split()]
	for e in map(int,raw_input().split()):
		mod=e%d
		dic[mod].append(((e-mod)//d-t,(e-mod)//d+t))
	print(sum(checkio(v) for k,v in dic.items()))
0