結果
| 問題 |
No.1394 Changing Problems
|
| コンテスト | |
| ユーザー |
 chineristAC
|
| 提出日時 | 2020-09-10 23:41:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,037 bytes |
| コンパイル時間 | 170 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 127,748 KB |
| 最終ジャッジ日時 | 2024-07-04 19:25:34 |
| 合計ジャッジ時間 | 9,928 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 RE * 2 |
| other | AC * 1 WA * 17 RE * 11 |
ソースコード
class LazySegmentTree():
__slots__ = ["merge","merge_unit","operate","merge_operate","operate_unit","n","data","lazy"]
def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
self.merge=merge
self.merge_unit=merge_unit
self.operate=operate
self.merge_operate=merge_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(self,v):
ope = self.lazy[v]
if ope == self.operate_unit:
return
self.lazy[v]=self.operate_unit
self.data[(v<<1)]=self.operate(self.data[(v<<1)],ope)
self.data[(v<<1)+1]=self.operate(self.data[(v<<1)+1],ope)
self.lazy[v<<1]=self.merge_operate(self.lazy[(v<<1)],ope)
self.lazy[(v<<1)+1]=self.merge_operate(self.lazy[(v<<1)+1],ope)
def propagate_above(self,i):
m=i.bit_length()-1
for bit in range(m,0,-1):
v=i>>bit
self.propagate(v)
def remerge_above(self,i):
while i:
c = self.merge(self.data[i],self.data[i^1])
i>>=1
self.data[i]=self.operate(c,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
self.propagate_above(l0)
self.propagate_above(r0)
while l<r:
if l&1:
self.data[l]=self.operate(self.data[l],x)
self.lazy[l]=self.merge_operate(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.merge_operate(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
def bisect_l(self,l,r,x):
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)
Lmin = -1
Rmin = -1
while l<r:
if l & 1:
if self.data[l] <= x and Lmin==-1:
Lmin = l
l += 1
if r & 1:
if self.data[r-1] <=x:
Rmin = r-1
l >>= 1
r >>= 1
res = -1
if Lmin != -1:
pos = Lmin
while pos<self.num:
self.propagate(pos)
if self.data[2 * pos] <=x:
pos = 2 * pos
else:
pos = 2 * pos +1
res = pos-self.num
if Rmin != -1:
pos = Rmin
while pos<self.num:
self.propagate(pos)
if self.data[2 * pos] <=x:
pos = 2 * pos
else:
pos = 2 * pos +1
if res==-1:
res = pos-self.num
else:
res = min(res,pos-self.num)
return res
import sys,heapq
from operator import add
input = sys.stdin.readline
mask = (1<<20) -1
N = int(input())
A = list(map(int,input().split()))
def Divmod(val):
x = val>>20
y = val&mask
return (x-N,y)
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]+N)<<20)+i for i in range(N-1)]
def operate(x,y):
if y>=0:
return x+(y<<20)
else:
return x-((-y)<<20)
LST = LazySegmentTree(N-1,init,min,1<<60,operate,add,0)
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 = Divmod(LST.query(0,lower_r))
if t1_r != -1 and t1_q + Qsum <= lower_q:
t1_q, t1_r = lower_q+1-Qsum, LST.bisect_l(0,lower_r,-1+((lower_q+2-Qsum + N)<<20))
t2_q,t2_r = Divmod(LST.query(lower_r,N-1))
if t2_r != -1 and t2_q + Qsum < lower_q:
t2_q,t2_r = lower_q-Qsum,LST.bisect_l(lower_r,N-1,-1+((lower_q+1-Qsum + N)<<20))
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)
if N==1:
solve_one()
else:
solve_not_one()