結果

問題 No.1496 不思議な数え上げ
コンテスト
ユーザー tpyneriver
提出日時 2021-04-07 00:29:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 620 ms / 3,000 ms
コード長 3,703 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 144,952 KB
最終ジャッジ日時 2024-07-16 03:38:54
合計ジャッジ時間 23,240 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = min):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            pre = self.intv
            for idx in (SR + SL[::-1]):
                if check(self.segf(self.data[idx], pre)):
                    break
                else:
                    pre = self.segf(self.data[idx], pre)
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(self.data[2*idx+1], pre)):
                    idx = 2*idx + 1
                else:
                    pre = self.segf(self.data[2*idx+1], pre)
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.intv
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0

INF = 10**9+7

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
A = [None] + list(map(int, sys.stdin.readline().split()))


Pinv = [None]*(N+1)
SP = P[:]+ [0]
for i in range(N):
    Pinv[P[i]] = i
    SP[i] += SP[i-1]

T = Segtree(P, INF)
stack = [(0, N)]
Ans = [None]*(N+1)

cnt = 0

while stack:
    l, r = stack.pop()
    p = T.query(l, r)
    m = Pinv[p]
    a = A[p]
    
    ans = 0
    if m-l < r-m:
        for x in range(l, m+1):
            ok = m-1
            ng = r
            while abs(ok-ng) > 1:
                med = (ok+ng)//2
                if SP[med] - SP[x-1] <= a:
                    ok = med
                else:
                    ng = med
            ans += ok-m+1
    else:
        for x in range(m, r):
            ok = m+1
            ng = l-1
            while abs(ok-ng) > 1:
                med = (ok+ng)//2
                if SP[x] - SP[med-1] <= a:
                    ok = med
                else:
                    ng = med
            ans += m-ok+1
            
    Ans[p] = ans
    if l < m:
        stack.append((l, m))
    if m+1 < r:
        stack.append((m+1, r))

print('\n'.join(map(str, Ans[1:])))
0