結果
問題 | No.1167 Graduation Trip |
ユーザー | Mitarushi |
提出日時 | 2020-08-11 22:49:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,466 ms / 4,000 ms |
コード長 | 1,600 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 109,228 KB |
最終ジャッジ日時 | 2024-04-17 17:46:24 |
合計ジャッジ時間 | 37,188 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,364 ms
108,904 KB |
testcase_01 | AC | 1,177 ms
106,092 KB |
testcase_02 | AC | 1,029 ms
102,016 KB |
testcase_03 | AC | 1,349 ms
108,828 KB |
testcase_04 | AC | 1,390 ms
108,584 KB |
testcase_05 | AC | 1,460 ms
106,296 KB |
testcase_06 | AC | 1,396 ms
108,724 KB |
testcase_07 | AC | 1,160 ms
105,592 KB |
testcase_08 | AC | 977 ms
102,748 KB |
testcase_09 | AC | 1,271 ms
107,796 KB |
testcase_10 | AC | 2,458 ms
109,168 KB |
testcase_11 | AC | 1,809 ms
108,932 KB |
testcase_12 | AC | 2,466 ms
108,916 KB |
testcase_13 | AC | 1,703 ms
109,188 KB |
testcase_14 | AC | 1,820 ms
108,920 KB |
testcase_15 | AC | 1,505 ms
106,612 KB |
testcase_16 | AC | 1,294 ms
103,204 KB |
testcase_17 | AC | 1,792 ms
108,936 KB |
testcase_18 | AC | 1,650 ms
108,552 KB |
testcase_19 | AC | 1,804 ms
109,228 KB |
testcase_20 | AC | 129 ms
77,584 KB |
testcase_21 | AC | 112 ms
77,084 KB |
testcase_22 | AC | 114 ms
77,480 KB |
testcase_23 | AC | 113 ms
77,456 KB |
testcase_24 | AC | 130 ms
77,512 KB |
testcase_25 | AC | 101 ms
76,940 KB |
testcase_26 | AC | 112 ms
77,156 KB |
testcase_27 | AC | 110 ms
77,324 KB |
testcase_28 | AC | 117 ms
77,200 KB |
testcase_29 | AC | 97 ms
77,256 KB |
testcase_30 | AC | 125 ms
81,204 KB |
testcase_31 | AC | 184 ms
86,792 KB |
testcase_32 | AC | 354 ms
89,076 KB |
testcase_33 | AC | 694 ms
104,720 KB |
testcase_34 | AC | 750 ms
105,760 KB |
testcase_35 | AC | 32 ms
53,116 KB |
testcase_36 | AC | 32 ms
53,756 KB |
testcase_37 | AC | 48 ms
66,984 KB |
ソースコード
import sys input = sys.stdin.readline n, q = [int(i) for i in input().split()] a = [int(i) for i in input().split()] mod = 10**9+7 def merge_base(a, b): c = a + b i = 1 k = 0 for _ in range(32): for j in range(k, len(c)): if (i & c[j]) != 0: break else: i <<= 1 continue c[j], c[k] = c[k], c[j] for j in range(k + 1, len(c)): if (i & c[j]) != 0: c[j] ^= c[k] i <<= 1 k += 1 return c[:k] class SparseTable: def __init__(self, a, func=max, one=-10**18): self.table = [a[:]] self.n = len(a) self.logn = self.n.bit_length() self.func = func self.one = one for i in map(lambda x: 1 << x, range(self.logn - 1)): self.table.append([]) for j in range(self.n - i * 2 + 1): self.table[-1].append(self.func(self.table[-2][j], self.table[-2][j + i])) def get_section(self, i, j): length = j - i log = length.bit_length() - 1 if length <= 0: return self.one return self.func(self.table[log][i], self.table[log][j - (1 << log)]) sp = SparseTable([[i] if i != 0 else[] for i in a], merge_base, []) for _ in range(q): m = int(input()) b = [0] for i in input().split(): b.append(int(i)) b.append(n) power = n for i in range(m + 1): j, k = b[i], b[i+1] power -= len(sp.get_section(j, k)) print(pow(2, power, mod))