結果
問題 | No.1394 Changing Problems |
ユーザー | chineristAC |
提出日時 | 2021-02-09 01:33:17 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,957 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 87,000 KB |
実行使用メモリ | 279,304 KB |
最終ジャッジ日時 | 2023-09-20 10:25:19 |
合計ジャッジ時間 | 36,735 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,116 KB |
testcase_01 | AC | 77 ms
71,308 KB |
testcase_02 | AC | 77 ms
71,308 KB |
testcase_03 | AC | 76 ms
71,108 KB |
testcase_04 | AC | 77 ms
71,316 KB |
testcase_05 | AC | 1,146 ms
225,940 KB |
testcase_06 | AC | 1,508 ms
258,016 KB |
testcase_07 | AC | 107 ms
75,544 KB |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | AC | 280 ms
82,736 KB |
testcase_11 | AC | 277 ms
82,968 KB |
testcase_12 | AC | 282 ms
84,776 KB |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | AC | 1,995 ms
274,144 KB |
testcase_17 | AC | 1,959 ms
279,304 KB |
testcase_18 | AC | 1,917 ms
268,636 KB |
testcase_19 | AC | 1,756 ms
265,840 KB |
testcase_20 | AC | 1,827 ms
271,968 KB |
testcase_21 | AC | 1,710 ms
266,476 KB |
testcase_22 | AC | 1,814 ms
269,148 KB |
testcase_23 | AC | 1,865 ms
271,104 KB |
testcase_24 | AC | 1,908 ms
269,584 KB |
testcase_25 | AC | 2,017 ms
277,336 KB |
testcase_26 | AC | 857 ms
166,848 KB |
testcase_27 | AC | 771 ms
166,456 KB |
testcase_28 | AC | 795 ms
167,216 KB |
testcase_29 | AC | 723 ms
165,460 KB |
testcase_30 | AC | 692 ms
163,736 KB |
testcase_31 | AC | 691 ms
165,836 KB |
ソースコード
class SegmentTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 << (n - 1).bit_length() self.tree = [ide_ele] * 2 * self.num for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: k >>= 1 self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1]) def query(self, l, r): res = self.ide_ele l += self.num r += self.num right = [] while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: right.append(self.tree[r-1]) l >>= 1 r >>= 1 for x in right[::-1]: res = res = self.segfunc(res, x) return res def bisect_l(self,l,r,x): l += self.num r += self.num midx = -1 right = [] val = self.query(0,l) while l<r: if l & 1: val = self.segfunc(val,self.tree[l]) if val[1] <= x and midx == -1: midx = l l += 1 if r & 1: right.append(r-1) l >>= 1 r >>= 1 right = right[::-1] for r in right: val = self.segfunc(val,self.tree[r]) if val[1] <= x and midx == -1: midx = r if midx == -1: return -1 while midx < self.num: tmp = self.segfunc(val,self.tree[2 * pos]) if tmp[1] <= x: pos = 2 * pos else: val = tmp pos = 2 * pos + 1 return pos - self.num import sys from heapq import heapify,heappop,heappush input = sys.stdin.readline def segfunc(x,y): val_x,m_x,idx = x val_y,m_y,idy = y val = val_x + val_y if m_x <= val_x + m_y: m = m_x id = idx else: m = val_x + m_y id = idy return (val,m,id) ide_ele = (0,10**15,10**15) N = int(input()) A = list(map(int,input().split())) if N==1: Q = int(input()) for _ in range(Q): i,x = map(int,input().split()) A[0] = x print(A[0]+1) exit() 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 heappush(Max_que,(-a,i)) init = [((r!=0)-init[r],(r!=0)-init[r],r) for r in range(N-1)] Seg = SegmentTree(init,segfunc,ide_ele) init = [(r!=0)-init[r][0] for r in range(N-1)] for _ in range(int(input())): 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) init[pre_r] -= 1 Seg.update(pre_r,((pre_r!=0)-init[pre_r],(pre_r!=0)-init[pre_r],pre_r)) next_r = (x+1) % (N-1) init[next_r] += 1 Seg.update(next_r,((next_r!=0)-init[next_r],(next_r!=0)-init[next_r],next_r)) A[i] = x heappush(Max_que,(-x,i)) while -Max_que[0][0] != A[Max_que[0][1]]: 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 = Seg.query(0,lower_r) t1_q,t1_r = t1[1],t1[2] if t1_r!=10**15 and t1_q + Qsum <= lower_q: t1_q,t1_r = lower_q + 1 - Qsum , Seg.bisect(0,lower_r,lower_q+1-Qsum) t2 = Seg.query(lower_r,N-1) t2_q,t2_r = t1[0]+t2[1],t2[2] if t2_r!=10**15 and t2_q + Qsum < lower_q: t2_q,t2_r = lower_q - Qsum, Seg.bisect(lower_r,N-1,lower_q-Qsum) res = min((t1_q + Qsum) * (N-1) + t1_r ,(t2_q + Qsum) * (N-1) +t2_r) print(res)