結果

問題 No.2821 A[i] ← 2A[j] - A[i]
ユーザー 👑 p-adicp-adic
提出日時 2024-07-26 23:13:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,429 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 121,408 KB
最終ジャッジ日時 2024-07-26 23:13:48
合計ジャッジ時間 4,079 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
82,760 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class TwoByTwoMatrix:
	zero=None
	one=None

	def __init__(self,M00,M01,M10,M11):
		self.M00 = M00
		self.M01 = M01
		self.M10 = M10
		self.M11 = M11
	def copy(self):
		return self.__class__(self.M00,self.M01,self.M10,self.M11)

	def __eq__(self,other):
		return self.M00 == other.M00 and self.M01 == other.M01 and self.M10 == other.M10 and self.M11 == other.M11
	def __ne__(self,other):
		return not( self == other )

	def __iadd__(self,other):
		self.M00 += other.M00
		self.M01 += other.M01
		self.M10 += other.M10
		self.M11 += other.M11
		return self
	def __add__(self,other):
		M = self.copy()
		M += other
		return M

	def __isub__(self,other):
		self.M00 -= other.M00
		self.M01 -= other.M01
		self.M10 -= other.M10
		self.M11 -= other.M11
		return self
	def __sub__(self,other):
		M = self.copy()
		M -= other
		return M
	def __neg__(self):
		return self.__class__(-self.M00,-self.M01,-self.M10,-self.M11)

	def __mul__(self,other):
		return self.__class__(self.M00 * other.M00 + self.M01 * other.M10,self.M00 * other.M01 + self.M01 * other.M11,self.M10 * other.M00 + self.M11 * other.M10,self.M10 * other.M01 + self.M11 * other.M11)
	def __imul__(self,other):
		self.M00 , self.M01 , self.M10 , self.M11 = self.M00 * other.M00 + self.M01 * other.M10 , self.M00 * other.M01 + self.M01 * other.M11 , self.M10 * other.M00 + self.M11 * other.M10 , self.M10 * other.M01 + self.M11 * other.M11
		return self
	def ScalarMultiply(self,x):
		self.M00 *= x
		self.M01 *= x
		self.M10 *= x
		self.M11 *= x
		return self

	def det(self):
		return self.M00 * self.M11 - self.M01 * self.M10
	def tr(self):
		return self.M00 + self.M11

	def Adjugate(self):
		return self.__class__( self.M11 , - self.M01 , - self.M10 , self.M00 )
	def Inverse(self):
		return self.Adjugate().ScalarMultiply( 1 / self.det() )
		#d = self.det()
		#assert( d in [1,-1] ) #For the case of integer coefficients
		#return self.Adjugate().ScalarMultiply( d )
	def __truediv__(self,other):
		return self * other.Inverse()
	def __itruediv__(self,other):
		self *= other.Inverse()
		return self

	def __pow__(self,n): #Supported only when n>=0
		answer = self.__class__.one.copy()
		power = self.copy()
		while n > 0:
			if n&1:answer *= power
			power.Square()
			n >>= 1
		return answer
	def __xor__(self,n):
		return self.Inverse()**(-n)if n < 0 else self ** n

	#private:
	def Square(self):
		self.M00 , self.M01 , self.M10 , self.M11 = self.M00 ** 2 + self.M01 * self.M10 , ( self.M00 + self.M11 ) * self.M01 , self.M10 * ( self.M00 + self.M11 ) , self.M10 * self.M01 + self.M11 ** 2
TwoByTwoMatrix.zero = TwoByTwoMatrix(0,0,0,0) #User's definition
TwoByTwoMatrix.one = TwoByTwoMatrix(1,0,0,1) #User's definition

class TwoByOneMatrix:
	zero=None

	def __init__(self,M0,M1):
		self.M0 = M0
		self.M1 = M1
	def copy(self):
		return self.__class__(self.M0,self.M1)

	def __eq__(self,other):
		return self.M0 == other.M0 and self.M1 == other.M1
	def __ne__(self,other):
		return not( self == other )

	def __iadd__(self,other):
		self.M0 += other.M0
		self.M1 += other.M1
		return self
	def __add__(self,other):
		M = self.copy()
		M += other
		return M

	def __isub__(self,other):
		self.M0 -= other.M0
		self.M1 -= other.M1
		return self
	def __sub__(self,other):
		M = self.copy()
		M -= other
		return M
	def __neg__(self):
		return self.__class__(-self.M0,-self.M1)

	def __rmul__(self,T):
		return self.copy().Act(T)
	def Act(self,T,n=1):
		if n==1:T.M00 * self.M0 + T.M01 * self.M1 , T.M10 * self.M0 + T.M11 * self.M1
		elif n:
			if n>0:p = T.copy()
			else:n , p = -n , T.Inverse()
			while n:
				if n&1:self.M0 , self.M1 = p.M00 * self.M0 + p.M01 * self.M1 , p.M10 * self.M0 + p.M11 * self.M1
				n >>= 1
				p.Square()
		return self
	def ScalarMultiply(self,x):
		self.M0 *= x
		self.M1 *= x
		return self
TwoByOneMatrix.zero = TwoByOneMatrix(0,0) #User's definition

J=lambda:map(int,input().split())
N,*_=J()
A=list(J())
U=TwoByTwoMatrix(2,-1,1,0)
L=TwoByTwoMatrix(0,1,-1,2)
def f(i):
	global min;global max;l,r=0,1<<62
	if A[i]<min:A[i],min=min,A[i]
	if A[i]>max:A[i],max=max,A[i]
	if A[i]*2<min+max:
		v=TwoByOneMatrix(A[i],min)
		while l<r-1:
			m=(l+r)>>1;w=v.copy()
			if w.Act(U,m).M0>max:r=m
			else:l=m
		v.Act(U,l)
		A[i],min=v.M0,v.M1
	else:
		v=TwoByOneMatrix(max,A[i])
		while l<r-1:
			m=(l+r)>>1;w=v.copy()
			if w.Act(L,m).M1<min:r=m
			else:l=m
		v.Act(L,l)
		max,A[i]=v.M0,v.M1
min=max=A[0]
for i in range(N):f(i);print(max-min)
0