結果
問題 | No.1496 不思議な数え上げ |
ユーザー |
|
提出日時 | 2021-04-30 23:10:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 526 ms / 3,000 ms |
コード長 | 3,360 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 132,448 KB |
最終ジャッジ日時 | 2024-07-19 03:00:17 |
合計ジャッジ時間 | 20,248 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
import sysinput = 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 binarydef __init__(self, n, values=None):self.bit = [0]*(n+1)self.n = nself.total = 0if values is not None:for i,v in enumerate(values):self.add(i,v)self.total += vdef check(self):l = []prv = 0for i in range(1,self.n+1):val = self.query(i)l.append(val-prv)prv = valprint(" ".join(map(str, l)))#a1 ~ aiまでの和 O(logn)def query(self,i):res = 0while i > 0:res += self.bit[i]# res %= Mi -= i&(-i)return resdef get(self,i):return self.query(i+1) - self.query(i)#ai += x(logN)def add(self,i,x):i += 1if i==0:raise RuntimeErrorself.total += xwhile i <= self.n:self.bit[i] += x# self.bit[i] %= Mi += i&(-i)def index(self, v):"""a0,...,aiの和がv以上になる最小のindexを求める存在しないとき配列サイズを返す"""if v <= 0:return 0if self.total<v:return self.nx = 0r = 1while r < self.n:r = r << 1;ll = rwhile ll>0:if x+ll<self.n and self.bit[x+ll]<v:v -= self.bit[x+ll]x += llll = ll>>1return xn = 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] = ibit = 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)continuev = bit.query(ind)l = bit.index(v)if v==0:l = -1r = bit.index(v+1)val = 0if ind-l < r-ind:# if 1:for ii in range(l+1,ind+1):ok = ind+1bad = rif cum[bad]-cum[ii]<=a:val += (bad-ind)continueif cum[ok]-cum[ii]>a:continuewhile abs(ok-bad)>1:mm = (ok+bad)//2if cum[mm]-cum[ii]<=a:ok = mmelse:bad = mmval += (ok-ind)else:for ii in range(ind+1, r+1):ok = indbad = l+1if -cum[bad]+cum[ii]<=a:val += (-bad+ind+1)continueif -cum[ok]+cum[ii]>a:continuewhile abs(ok-bad)>1:mm = (ok+bad)//2if -cum[mm]+cum[ii]<=a:ok = mmelse:bad = mmval += (-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)))