結果
問題 | No.1233 割り切れない気持ち |
ユーザー | Shinya Fujita |
提出日時 | 2024-10-06 02:03:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,086 ms / 3,153 ms |
コード長 | 2,910 bytes |
コンパイル時間 | 359 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 125,824 KB |
最終ジャッジ日時 | 2024-10-06 02:03:27 |
合計ジャッジ時間 | 15,437 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
53,888 KB |
testcase_01 | AC | 48 ms
53,760 KB |
testcase_02 | AC | 55 ms
60,544 KB |
testcase_03 | AC | 83 ms
73,216 KB |
testcase_04 | AC | 85 ms
72,704 KB |
testcase_05 | AC | 53 ms
59,136 KB |
testcase_06 | AC | 55 ms
60,928 KB |
testcase_07 | AC | 238 ms
87,168 KB |
testcase_08 | AC | 360 ms
97,232 KB |
testcase_09 | AC | 668 ms
117,120 KB |
testcase_10 | AC | 707 ms
120,064 KB |
testcase_11 | AC | 204 ms
86,400 KB |
testcase_12 | AC | 802 ms
123,648 KB |
testcase_13 | AC | 803 ms
123,524 KB |
testcase_14 | AC | 768 ms
123,776 KB |
testcase_15 | AC | 811 ms
123,776 KB |
testcase_16 | AC | 834 ms
123,648 KB |
testcase_17 | AC | 127 ms
104,064 KB |
testcase_18 | AC | 1,086 ms
123,904 KB |
testcase_19 | AC | 162 ms
124,032 KB |
testcase_20 | AC | 124 ms
104,192 KB |
testcase_21 | AC | 134 ms
105,600 KB |
testcase_22 | AC | 160 ms
104,704 KB |
testcase_23 | AC | 136 ms
104,704 KB |
testcase_24 | AC | 135 ms
105,216 KB |
testcase_25 | AC | 135 ms
104,832 KB |
testcase_26 | AC | 137 ms
105,216 KB |
testcase_27 | AC | 179 ms
123,136 KB |
testcase_28 | AC | 184 ms
123,008 KB |
testcase_29 | AC | 182 ms
122,880 KB |
testcase_30 | AC | 198 ms
122,880 KB |
testcase_31 | AC | 181 ms
122,880 KB |
testcase_32 | AC | 177 ms
123,264 KB |
testcase_33 | AC | 179 ms
123,008 KB |
testcase_34 | AC | 177 ms
123,008 KB |
testcase_35 | AC | 179 ms
123,008 KB |
testcase_36 | AC | 205 ms
123,520 KB |
testcase_37 | AC | 49 ms
54,144 KB |
testcase_38 | AC | 229 ms
125,824 KB |
testcase_39 | AC | 635 ms
104,960 KB |
testcase_40 | AC | 653 ms
104,832 KB |
ソースコード
class SegmentTree: def __init__(self, a): self.padding = 0 self.n = len(a) self.N = 2 ** (self.n-1).bit_length() self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n) for i in range(2*self.N-2, 0, -2): self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1] def __len__(self): return self.n def __getitem__(self, i): return self.seg_data[self.N-1+i] def __setitem__(self, i, x): idx = self.N - 1 + i self.seg_data[idx] = x while idx: idx = (idx-1) // 2 self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2] def query(self, i, j): # [i, j) if i == j: return 0 else: idx1 = self.N - 1 + i idx2 = self.N - 2 + j # 閉区間にする result = self.padding while idx1 < idx2 + 1: if idx1&1 == 0: # idx1が偶数 result = result + self.seg_data[idx1] if idx2&1 == 1: # idx2が奇数 result = result + self.seg_data[idx2] idx2 -= 1 idx1 //= 2 idx2 = (idx2 - 1)//2 return result def kth_left_idx(self, fr, k): if self.query(0, fr+1) < k: return -1 remain = k now = fr + self.N - 1 while self.seg_data[now] < remain: if now % 2: remain -= self.seg_data[now] now -= 1 else: now = (now - 1) // 2 while now < self.N - 1: nl = 2*now + 1 nr = nl + 1 if self.seg_data[nr] < remain: remain -= self.seg_data[nr] now = nl else: now = nr return now - (self.N - 1) def kth_right_idx(self, fr, k): if self.query(fr, self.n) < k: return -1 remain = k now = fr + self.N - 1 while self.seg_data[now] < remain: if now % 2 == 0: remain -= self.seg_data[now] now += 1 else: now //= 2 while now < self.N - 1: nl = 2*now + 1 nr = nl + 1 if self.seg_data[nl] < remain: remain -= self.seg_data[nl] now = nr else: now = nl return now - (self.N - 1) from collections import defaultdict N = int(input()) A = list(map(int, input().split())) S = sum(A) maxA = max(A) cnt = defaultdict(int) st = SegmentTree([0] * (maxA + 1)) for a in A: cnt[a] += 1 st[a] += 1 ans = S * N for a, n in cnt.items(): left = a while left <= maxA: ans -= a*n*st.query(left, maxA+1) left += a print(ans)