結果

問題 No.1496 不思議な数え上げ
ユーザー tpynerivertpyneriver
提出日時 2021-04-07 00:29:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 683 ms / 3,000 ms
コード長 3,703 bytes
コンパイル時間 1,664 ms
コンパイル使用メモリ 86,928 KB
実行使用メモリ 146,076 KB
最終ジャッジ日時 2023-09-23 03:22:59
合計ジャッジ時間 29,162 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,276 KB
testcase_01 AC 74 ms
70,908 KB
testcase_02 AC 73 ms
71,304 KB
testcase_03 AC 514 ms
128,736 KB
testcase_04 AC 483 ms
128,904 KB
testcase_05 AC 483 ms
128,988 KB
testcase_06 AC 354 ms
128,784 KB
testcase_07 AC 354 ms
128,964 KB
testcase_08 AC 344 ms
128,588 KB
testcase_09 AC 350 ms
128,660 KB
testcase_10 AC 356 ms
128,752 KB
testcase_11 AC 352 ms
128,636 KB
testcase_12 AC 506 ms
142,640 KB
testcase_13 AC 370 ms
129,024 KB
testcase_14 AC 369 ms
128,948 KB
testcase_15 AC 369 ms
128,820 KB
testcase_16 AC 372 ms
128,844 KB
testcase_17 AC 593 ms
142,388 KB
testcase_18 AC 603 ms
142,448 KB
testcase_19 AC 591 ms
142,868 KB
testcase_20 AC 620 ms
129,000 KB
testcase_21 AC 604 ms
128,840 KB
testcase_22 AC 597 ms
129,060 KB
testcase_23 AC 610 ms
129,092 KB
testcase_24 AC 630 ms
128,836 KB
testcase_25 AC 597 ms
142,636 KB
testcase_26 AC 598 ms
142,532 KB
testcase_27 AC 651 ms
146,076 KB
testcase_28 AC 683 ms
142,868 KB
testcase_29 AC 636 ms
142,584 KB
testcase_30 AC 670 ms
143,076 KB
testcase_31 AC 636 ms
142,980 KB
testcase_32 AC 583 ms
137,820 KB
testcase_33 AC 422 ms
110,800 KB
testcase_34 AC 424 ms
107,084 KB
testcase_35 AC 142 ms
78,932 KB
testcase_36 AC 588 ms
138,020 KB
testcase_37 AC 443 ms
114,428 KB
testcase_38 AC 422 ms
110,288 KB
testcase_39 AC 498 ms
126,256 KB
testcase_40 AC 372 ms
101,536 KB
testcase_41 AC 495 ms
127,376 KB
権限があれば一括ダウンロードができます

ソースコード

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