結果
問題 | No.1496 不思議な数え上げ |
ユーザー | shotoyoo |
提出日時 | 2021-04-30 23:10:46 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 540 ms / 3,000 ms |
コード長 | 3,360 bytes |
コンパイル時間 | 1,615 ms |
コンパイル使用メモリ | 86,624 KB |
実行使用メモリ | 133,560 KB |
最終ジャッジ日時 | 2023-09-26 07:53:49 |
合計ジャッジ時間 | 21,343 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,220 KB |
testcase_01 | AC | 70 ms
71,188 KB |
testcase_02 | AC | 75 ms
71,112 KB |
testcase_03 | AC | 403 ms
132,160 KB |
testcase_04 | AC | 408 ms
131,964 KB |
testcase_05 | AC | 407 ms
132,388 KB |
testcase_06 | AC | 394 ms
132,140 KB |
testcase_07 | AC | 392 ms
132,204 KB |
testcase_08 | AC | 389 ms
132,216 KB |
testcase_09 | AC | 415 ms
132,216 KB |
testcase_10 | AC | 413 ms
132,292 KB |
testcase_11 | AC | 417 ms
132,108 KB |
testcase_12 | AC | 407 ms
132,508 KB |
testcase_13 | AC | 415 ms
132,168 KB |
testcase_14 | AC | 412 ms
132,200 KB |
testcase_15 | AC | 411 ms
132,120 KB |
testcase_16 | AC | 407 ms
132,372 KB |
testcase_17 | AC | 484 ms
132,624 KB |
testcase_18 | AC | 480 ms
132,556 KB |
testcase_19 | AC | 493 ms
132,480 KB |
testcase_20 | AC | 505 ms
132,012 KB |
testcase_21 | AC | 505 ms
132,052 KB |
testcase_22 | AC | 497 ms
132,208 KB |
testcase_23 | AC | 495 ms
133,560 KB |
testcase_24 | AC | 509 ms
132,100 KB |
testcase_25 | AC | 459 ms
132,428 KB |
testcase_26 | AC | 468 ms
132,260 KB |
testcase_27 | AC | 540 ms
130,520 KB |
testcase_28 | AC | 519 ms
128,796 KB |
testcase_29 | AC | 518 ms
128,788 KB |
testcase_30 | AC | 517 ms
130,664 KB |
testcase_31 | AC | 515 ms
128,684 KB |
testcase_32 | AC | 460 ms
124,376 KB |
testcase_33 | AC | 292 ms
103,172 KB |
testcase_34 | AC | 292 ms
101,956 KB |
testcase_35 | AC | 137 ms
79,564 KB |
testcase_36 | AC | 472 ms
124,264 KB |
testcase_37 | AC | 302 ms
106,336 KB |
testcase_38 | AC | 295 ms
105,212 KB |
testcase_39 | AC | 358 ms
114,360 KB |
testcase_40 | AC | 255 ms
97,996 KB |
testcase_41 | AC | 379 ms
113,520 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") class BIT: ### BIT binary def __init__(self, n, values=None): self.bit = [0]*(n+1) self.n = n self.total = 0 if values is not None: for i,v in enumerate(values): self.add(i,v) self.total += v def check(self): l = [] prv = 0 for i in range(1,self.n+1): val = self.query(i) l.append(val-prv) prv = val print(" ".join(map(str, l))) #a1 ~ aiまでの和 O(logn) def query(self,i): res = 0 while i > 0: res += self.bit[i] # res %= M i -= i&(-i) return res def get(self,i): return self.query(i+1) - self.query(i) #ai += x(logN) def add(self,i,x): i += 1 if i==0: raise RuntimeError self.total += x while i <= self.n: self.bit[i] += x # self.bit[i] %= M i += i&(-i) def index(self, v): """a0,...,aiの和がv以上になる最小のindexを求める 存在しないとき配列サイズを返す """ if v <= 0: return 0 if self.total<v: return self.n x = 0 r = 1 while r < self.n: r = r << 1; ll = r while ll>0: if x+ll<self.n and self.bit[x+ll]<v: v -= self.bit[x+ll] x += ll ll = ll>>1 return x n = int(input()) p = list(map(lambda i: int(i), input().split())) A = list(map(int, input().split())) cum = [0] for v in p: cum.append(cum[-1]+v) index = [-1]*(n+1) for i,v in enumerate(p): index[v] = i bit = BIT(n) ans = [] for i in range(1,n+1): a = A[i-1] ind = index[i] if a==0: bit.add(ind, 1) ans.append(0) continue v = bit.query(ind) l = bit.index(v) if v==0: l = -1 r = bit.index(v+1) val = 0 if ind-l < r-ind: # if 1: for ii in range(l+1,ind+1): ok = ind+1 bad = r if cum[bad]-cum[ii]<=a: val += (bad-ind) continue if cum[ok]-cum[ii]>a: continue while abs(ok-bad)>1: mm = (ok+bad)//2 if cum[mm]-cum[ii]<=a: ok = mm else: bad = mm val += (ok-ind) else: for ii in range(ind+1, r+1): ok = ind bad = l+1 if -cum[bad]+cum[ii]<=a: val += (-bad+ind+1) continue if -cum[ok]+cum[ii]>a: continue while abs(ok-bad)>1: mm = (ok+bad)//2 if -cum[mm]+cum[ii]<=a: ok = mm else: bad = mm val += (-ok+ind+1) # j = ind+1 # val = 0 # for ii in range(l+1, ind+1): # while j+1<=r and cum[j+1]-cum[ii]<=a: # j += 1 # if cum[j]-cum[ii]<=a: # val += (j-ind) bit.add(ind, 1) ans.append(val) write("\n".join(map(str, ans)))