結果
| 問題 |
No.1394 Changing Problems
|
| コンテスト | |
| ユーザー |
 chineristAC
|
| 提出日時 | 2020-09-07 19:12:46 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,288 bytes |
| コンパイル時間 | 175 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 102,272 KB |
| 最終ジャッジ日時 | 2024-07-04 19:24:22 |
| 合計ジャッジ時間 | 5,318 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 RE * 2 |
| other | WA * 26 RE * 3 |
ソースコード
class LazySegmentTree():
def __init__(self,n,init,merge=min,merge_unit=(10**18,-1),operate=lambda x,y:(x[0]+y,x[1]),operate_unit=0):
self.merge=merge
self.merge_unit=merge_unit
self.operate=operate
self.operate_unit=operate_unit
self.n=(n-1).bit_length()
self.data=[merge_unit for i in range(1<<(self.n+1))]
self.lazy=[operate_unit for i in range(1<<(self.n+1))]
if init:
for i in range(n):
self.data[2**self.n+i]=init[i]
for i in range(2**self.n-1,0,-1):
self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])
def propagate_above(self,i):
m=i.bit_length()-1
for bit in range(m,0,-1):
v=i>>bit
add=self.lazy[v]
self.lazy[v]=self.operate_unit
self.data[2*v]=self.operate(self.data[2*v],add)
self.data[2*v+1]=self.operate(self.data[2*v+1],add)
self.lazy[2*v]=self.lazy[2*v] + add
self.lazy[2*v+1]=self.lazy[2*v+1] + add
def remerge_above(self,i):
while i:
i>>=1
self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),self.lazy[i])
def update(self,l,r,x):
l+=1<<self.n
r+=1<<self.n
l0=l//(l&-l)
r0=r//(r&-r)-1
while l<r:
if l&1:
self.data[l]=self.operate(self.data[l],x)
self.lazy[l]=self.lazy[l] + x
l+=1
if r&1:
self.data[r-1]=self.operate(self.data[r-1],x)
self.lazy[r-1]=self.lazy[r-1] + x
l>>=1
r>>=1
self.remerge_above(l0)
self.remerge_above(r0)
def query(self,l,r):
l+=1<<self.n
r+=1<<self.n
l0=l//(l&-l)
r0=r//(r&-r)-1
self.propagate_above(l0)
self.propagate_above(r0)
res=self.merge_unit
while l<r:
if l&1:
res=self.merge(res,self.data[l])
l+=1
if r&1:
res=self.merge(res,self.data[r-1])
l>>=1
r>>=1
return res
import sys,heapq
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
def solve_not_one():
init = [0]*(N-1)
Qsum = 0
Max_que = []
for i in range(N):
a = A[i]
q = (a+1) // (N-1)
r = (a+1) % (N-1)
init[r] += 1
Qsum += q
heapq.heappush(Max_que,(-a,i))
for i in range(1,N-1):
init[i] += init[i-1]
init = [(i-init[i],i) for i in range(N-1)]
LST = LazySegmentTree(N-1,init)
Q = int(input())
for _ in range(Q):
query = tuple(map(int,input().split()))
if query[0] == 1:
gomi,i,x = query
i -= 1
Qsum -= (A[i]+1) // (N-1)
Qsum += (x+1) // (N-1)
pre_r = (A[i]+1) % (N-1)
LST.update(pre_r,N-1,1)
next_r = (x+1) % (N-1)
LST.update(next_r,N-1,-1)
A[i] = x
heapq.heappush(Max_que,(-x,i))
else:
while -Max_que[0][0] != A[Max_que[0][1]]:
heapq.heappop(Max_que)
lower = -Max_que[0][0] - (N-2)
if lower<=0:
print(0)
continue
lower_q = lower//(N-1)
lower_r = lower%(N-1)
t1_q,t1_r = LST.query(0,lower_r)
if t1_r != -1 and t1_q + Qsum <= lower_q:
start = -1
end = lower_r-1
while end-start>1:
test = (end + start) // 2
if LST.query(0,test+1)[0] + Qsum <= lower_q:
end = test
else:
start = test
t1_q, t1_r = lower_q+1-Qsum, end
t2_q,t2_r = LST.query(lower_r,N-1)
if t2_r != -1 and t2_q + Qsum < lower_q:
start = lower_r-1
end = N-2
while end-start>1:
test = (end + start) // 2
if LST.query(lower_r,test+1)[0] + Qsum < lower_q:
end = test
else:
start = test
t2_q,t2_r = lower_q-Qsum,end
res = min((t1_q + Qsum) * (N-1) + t1_r ,(t2_q + Qsum) * (N-1) +t2_r)
assert(res>=lower)
print(res)
def solve_one():
Q = int(input())
for _ in range(Q):
query = tuple(map(int,input().split()))
if query[0] == 1:
A[0] = query[2]
else:
print(A[0]+1)
def brute_force():
def solve():
R = [0]*(N-1)
Qsum = 0
for a in A:
q = (a+1)//(N-1)
r = (a+1)%(N-1)
Qsum += q
R[r] += 1
for i in range(1,N-1):
R[i] += R[i-1]
Amax = max(A)
lower = Amax - (N-2)
Qmax = lower // (N-1)
Rmax = lower % (N-1)
if lower<=0:
return 0
res = 10**18
for r in range(N-1):
if r<Rmax:
tmp_q = Qsum + r - R[r]
if tmp_q <= Qmax:
tmp_q = Qmax + 1
tmp = (N-1) * tmp_q + r
else:
tmp_q = Qsum + r - R[r]
if tmp_q < Qmax:
tmp_q = Qmax
tmp = (N-1) * tmp_q + r
res = min(res,tmp)
return res
def debug():
q = [0 for i in range(N)]
r = [0 for i in range(N)]
test = [0 for i in range(N-1)]
Qsum = 0
for i in range(N):
a = A[i]
Q = (a+1)//(N-1)
R = (a+1)%(N-1)
Qsum += Q
q[i] = Q
r[i] = R
test[R] += 1
for i in range(1,N-1):
test[i] += test[i-1]
print("q:",*q)
print("r:",*r)
print("test:",*test)
print(Qsum)
Q = int(input())
for _ in range(Q):
query = tuple(map(int,input().split()))
if query[0] == 1:
gomi,i,x = query
A[i-1] = x
else:
print(solve())
if N==1:
solve_one()
elif N<=5000:
brute_force()
else:
exit()