結果
問題 | No.404 部分門松列 |
ユーザー |
![]() |
提出日時 | 2020-04-09 01:22:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 708 ms / 2,000 ms |
コード長 | 2,504 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 176,308 KB |
最終ジャッジ日時 | 2024-07-19 05:58:37 |
合計ジャッジ時間 | 14,425 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#!/usr/bin/ python3.8import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesfrom bisect import bisect_rightclass BinaryIndexedTree():def __init__(self, seq):self.size = len(seq)self.depth = self.size.bit_length()self.build(seq)def build(self, seq):data = seqsize = self.sizefor i, x in enumerate(data):j = i + (i & (-i))if j < size:data[j] += data[i]self.data = datadef __repr__(self):return self.data.__repr__()def get_sum(self, i):data = self.datas = 0while i:s += data[i]i -= i & -ireturn sdef add(self, i, x):data = self.datasize = self.sizewhile i < size:data[i] += xi += i & -idef find_kth_element(self, k):data = self.datasize = self.sizex, sx = 0, 0dx = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):dx = (1 << i)if x + dx >= size:continuey = x + dxsy = sx + data[y]if sy < k:x, sx = y, syreturn x + 1N = int(readline())A = tuple(map(int, readline().split()))A_nums = [0] + sorted(set(A))convert = {x: i for i, x in enumerate(A_nums)}inds = [[] for _ in range(len(A_nums))]for i, x in enumerate(A, 1):r = convert[x]inds[r].append(i)filled = 0bit = BinaryIndexedTree([0] * (N + 1))imos = [0] * (N + 1)count = [0] * (N + 1)for ind in inds:n = len(ind)for m, i in enumerate(ind):if m < n - 1:imos[i + 1] += (m + 1) * (n - m - 1)imos[i] -= m * (n - m)left = bit.get_sum(i)right = filled - leftcount[i] = left * rightleft = i - 1 - m - leftright = N - filled - n - leftcount[i] += left * rightfor i in ind:bit.add(i, 1)filled += nfor i in range(1, N + 1):imos[i] += imos[i - 1]count[i] -= imos[i]num_to_cnt = [0] * len(A_nums)for x, y in zip(A, count[1:]):r = convert[x]num_to_cnt[r] += yfor i in range(1, len(num_to_cnt)):num_to_cnt[i] += num_to_cnt[i - 1]Q = int(readline())m = map(int, read().split())for L, H in zip(m, m):x = num_to_cnt[bisect_right(A_nums, H) - 1] - num_to_cnt[bisect_right(A_nums, L - 1) - 1]print(x)