結果
| 問題 | No.1394 Changing Problems |
| ユーザー |
 chineristAC
|
| 提出日時 | 2020-09-30 00:21:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,197 ms / 3,000 ms |
| コード長 | 5,908 bytes |
| コンパイル時間 | 336 ms |
| コンパイル使用メモリ | 86,828 KB |
| 実行使用メモリ | 143,396 KB |
| 最終ジャッジ日時 | 2023-09-18 02:45:01 |
| 合計ジャッジ時間 | 27,155 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 79 ms
71,040 KB |
| testcase_01 | AC | 80 ms
71,340 KB |
| testcase_02 | AC | 80 ms
71,120 KB |
| testcase_03 | AC | 79 ms
71,128 KB |
| testcase_04 | AC | 80 ms
71,124 KB |
| testcase_05 | AC | 891 ms
143,396 KB |
| testcase_06 | AC | 882 ms
127,476 KB |
| testcase_07 | AC | 89 ms
75,508 KB |
| testcase_08 | AC | 328 ms
82,068 KB |
| testcase_09 | AC | 345 ms
82,976 KB |
| testcase_10 | AC | 393 ms
83,424 KB |
| testcase_11 | AC | 339 ms
82,552 KB |
| testcase_12 | AC | 345 ms
82,848 KB |
| testcase_13 | AC | 1,194 ms
129,872 KB |
| testcase_14 | AC | 1,121 ms
128,800 KB |
| testcase_15 | AC | 1,197 ms
128,812 KB |
| testcase_16 | AC | 1,142 ms
129,444 KB |
| testcase_17 | AC | 1,099 ms
130,276 KB |
| testcase_18 | AC | 1,109 ms
129,820 KB |
| testcase_19 | AC | 1,068 ms
129,904 KB |
| testcase_20 | AC | 1,091 ms
130,484 KB |
| testcase_21 | AC | 1,140 ms
130,128 KB |
| testcase_22 | AC | 1,084 ms
130,092 KB |
| testcase_23 | AC | 1,089 ms
129,392 KB |
| testcase_24 | AC | 1,193 ms
130,448 KB |
| testcase_25 | AC | 1,176 ms
131,500 KB |
| testcase_26 | AC | 893 ms
130,092 KB |
| testcase_27 | AC | 932 ms
131,636 KB |
| testcase_28 | AC | 895 ms
131,192 KB |
| testcase_29 | AC | 776 ms
127,364 KB |
| testcase_30 | AC | 743 ms
127,652 KB |
| testcase_31 | AC | 750 ms
127,224 KB |
ソースコード
class LazySegmentTree():
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.num = 1<<self.n
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[2*v]=self.operate(self.data[2*v],ope)
self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+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:
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.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())
assert(1<=N<=2*10**5)
A = list(map(int,input().split()))
assert(len(A)==N)
assert(all(0<=A[i]<=10**9 for i in range(N)))
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())
assert(1<=Q<=10**5)
for _ in range(Q):
i,x = map(int,input().split())
assert(1<=i<=N)
assert(0<=x<=10**9)
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))
#問題の答え
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())
assert(1<=Q<=10**5)
for _ in range(Q):
i,x = map(int,input().split())
assert(1<=i<=N)
assert(0<=x<=10**9)
A[0] = x
print(A[0]+1)
if N==1:
solve_one()
else:
solve_not_one()