結果
問題 | No.1167 Graduation Trip |
ユーザー | Mitarushi |
提出日時 | 2020-08-11 22:47:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,616 ms / 4,000 ms |
コード長 | 1,600 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 109,824 KB |
最終ジャッジ日時 | 2024-04-17 17:45:30 |
合計ジャッジ時間 | 41,963 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,795 ms
109,184 KB |
testcase_01 | AC | 1,299 ms
106,496 KB |
testcase_02 | AC | 1,181 ms
102,912 KB |
testcase_03 | AC | 1,565 ms
109,056 KB |
testcase_04 | AC | 1,622 ms
109,312 KB |
testcase_05 | AC | 1,803 ms
107,008 KB |
testcase_06 | AC | 1,573 ms
109,184 KB |
testcase_07 | AC | 1,306 ms
105,420 KB |
testcase_08 | AC | 1,091 ms
102,952 KB |
testcase_09 | AC | 1,483 ms
107,900 KB |
testcase_10 | AC | 2,037 ms
109,440 KB |
testcase_11 | AC | 2,421 ms
109,568 KB |
testcase_12 | AC | 2,616 ms
109,440 KB |
testcase_13 | AC | 2,073 ms
109,824 KB |
testcase_14 | AC | 1,941 ms
109,696 KB |
testcase_15 | AC | 1,816 ms
106,648 KB |
testcase_16 | AC | 1,520 ms
103,472 KB |
testcase_17 | AC | 2,019 ms
109,616 KB |
testcase_18 | AC | 1,950 ms
109,184 KB |
testcase_19 | AC | 1,969 ms
109,628 KB |
testcase_20 | AC | 127 ms
77,132 KB |
testcase_21 | AC | 121 ms
77,616 KB |
testcase_22 | AC | 124 ms
77,416 KB |
testcase_23 | AC | 138 ms
77,568 KB |
testcase_24 | AC | 136 ms
77,532 KB |
testcase_25 | AC | 110 ms
77,312 KB |
testcase_26 | AC | 108 ms
77,228 KB |
testcase_27 | AC | 122 ms
77,952 KB |
testcase_28 | AC | 112 ms
77,352 KB |
testcase_29 | AC | 113 ms
77,716 KB |
testcase_30 | AC | 125 ms
81,536 KB |
testcase_31 | AC | 198 ms
87,168 KB |
testcase_32 | AC | 416 ms
89,488 KB |
testcase_33 | AC | 780 ms
104,448 KB |
testcase_34 | AC | 909 ms
106,880 KB |
testcase_35 | AC | 32 ms
52,864 KB |
testcase_36 | AC | 31 ms
52,480 KB |
testcase_37 | AC | 46 ms
65,664 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(40): 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))