結果

問題 No.1394 Changing Problems
ユーザー chineristACchineristAC
提出日時 2020-09-25 09:15:21
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 6,328 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 130,640 KB
最終ジャッジ日時 2024-07-04 19:28:57
合計ジャッジ時間 7,474 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 WA -
testcase_07 RE -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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(Qlimit = 0):

    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())
    if Qlimit and N>=5000:
        Q = Qlimit
    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()
else:
    brute_force(Qlimit=20)
0