結果
問題 | No.2046 Ans Mod? Mod Ans! |
ユーザー |
|
提出日時 | 2022-08-19 22:16:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 606 ms / 4,000 ms |
コード長 | 1,205 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 106,624 KB |
最終ジャッジ日時 | 2024-12-16 08:20:51 |
合計ジャッジ時間 | 6,324 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict,Counter from heapq import heapify,heappop,heappush from itertools import cycle, permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) class BIT(): def __init__(self,n,mod=0): self.BIT = [0]*(n+1) self.num = n self.mod = mod """ return A[1] + A[2] + ... A[idx] in O(log n) """ def query(self,idx): res_sum = 0 mod = self.mod while idx > 0: res_sum += self.BIT[idx] if mod: res_sum %= mod idx -= idx&(-idx) return res_sum """ A[idx] += in O(log n) """ def update(self,idx,x): mod = self.mod while idx <= self.num: self.BIT[idx] += x if mod: self.BIT[idx] %= mod idx += idx&(-idx) return N = int(input()) A = li() A.sort() res = 0 fw = BIT(3*10**5) for i in range(N)[::-1]: res += A[i] * (N-2*i-1) for k in range(A[i],3*10**5,A[i]): res += (N-i-1 - fw.query(k-1)) * A[i] fw.update(A[i],1) print(res)