結果
| 問題 | No.1394 Changing Problems |
| ユーザー |
 chineristAC
|
| 提出日時 | 2020-09-30 00:14:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,716 bytes |
| コンパイル時間 | 190 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 133,688 KB |
| 最終ジャッジ日時 | 2024-07-04 19:30:15 |
| 合計ジャッジ時間 | 24,977 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 43 ms
54,144 KB |
| testcase_01 | AC | 41 ms
54,144 KB |
| testcase_02 | AC | 41 ms
54,272 KB |
| testcase_03 | AC | 41 ms
54,272 KB |
| testcase_04 | AC | 39 ms
54,656 KB |
| testcase_05 | AC | 792 ms
133,688 KB |
| testcase_06 | AC | 801 ms
115,660 KB |
| testcase_07 | RE | - |
| testcase_08 | AC | 274 ms
80,376 KB |
| testcase_09 | AC | 290 ms
79,940 KB |
| testcase_10 | AC | 341 ms
82,636 KB |
| testcase_11 | AC | 283 ms
79,656 KB |
| testcase_12 | AC | 287 ms
79,708 KB |
| testcase_13 | AC | 1,095 ms
118,012 KB |
| testcase_14 | AC | 1,016 ms
116,484 KB |
| testcase_15 | AC | 1,096 ms
117,764 KB |
| testcase_16 | AC | 1,075 ms
124,488 KB |
| testcase_17 | AC | 1,009 ms
125,396 KB |
| testcase_18 | AC | 999 ms
123,980 KB |
| testcase_19 | AC | 980 ms
125,396 KB |
| testcase_20 | AC | 1,030 ms
124,112 KB |
| testcase_21 | AC | 1,063 ms
125,652 KB |
| testcase_22 | AC | 996 ms
124,984 KB |
| testcase_23 | AC | 1,000 ms
124,620 KB |
| testcase_24 | AC | 1,253 ms
125,628 KB |
| testcase_25 | AC | 1,253 ms
127,184 KB |
| testcase_26 | AC | 922 ms
125,544 KB |
| testcase_27 | AC | 961 ms
125,544 KB |
| testcase_28 | AC | 840 ms
125,540 KB |
| testcase_29 | AC | 683 ms
124,880 KB |
| testcase_30 | AC | 632 ms
123,248 KB |
| testcase_31 | AC | 672 ms
124,400 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())
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):
i,x = map(int,input().split())
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())
for _ in range(Q):
query = tuple(map(int,input().split()))
i,x = map(int,input().split())
A[0] = x
print(A[0]+1)
if N==1:
solve_one()
else:
solve_not_one()