結果
問題 |
No.2300 Substring OR Sum
|
ユーザー |
![]() |
提出日時 | 2024-03-19 12:32:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 668 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 107,880 KB |
最終ジャッジ日時 | 2024-09-30 05:25:41 |
合計ジャッジ時間 | 3,279 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
# ビット演算なのでビット桁ごとに計算、ORなので1があるかどうか # 入力例1の2の0乗桁は、1,1,0、つまり1のない区間は1,ある区間はN*(N+1)//2-1=5 N = int(input()) A = list(map(int, input().split())) ans = 0 for d in range(0, 30): zero_segment = 0 zero_count = 0 for a in A: if (a>>d)&1 == 0: zero_count += 1 else: zero_segment += zero_count*(zero_count+1)//2 zero_count = 0 zero_segment += zero_count*(zero_count+1)//2 calc = (1<<d)*(N*(N+1)//2-zero_segment) ans += calc #print('d', d, 'zero_segment', zero_segment, 'calc', calc) print(ans)