結果
問題 | No.1996 <>< |
ユーザー | nephrologist |
提出日時 | 2022-07-02 10:21:48 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,546 bytes |
コンパイル時間 | 505 ms |
コンパイル使用メモリ | 86,848 KB |
実行使用メモリ | 146,660 KB |
最終ジャッジ日時 | 2023-08-18 01:26:49 |
合計ジャッジ時間 | 27,883 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,208 KB |
testcase_01 | AC | 72 ms
71,252 KB |
testcase_02 | AC | 71 ms
71,112 KB |
testcase_03 | AC | 121 ms
76,276 KB |
testcase_04 | AC | 72 ms
71,156 KB |
testcase_05 | AC | 72 ms
71,140 KB |
testcase_06 | AC | 71 ms
71,320 KB |
testcase_07 | AC | 73 ms
71,156 KB |
testcase_08 | AC | 126 ms
78,292 KB |
testcase_09 | AC | 86 ms
76,120 KB |
testcase_10 | AC | 115 ms
77,496 KB |
testcase_11 | AC | 967 ms
112,076 KB |
testcase_12 | AC | 1,677 ms
144,792 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 1,772 ms
135,948 KB |
testcase_16 | AC | 1,585 ms
129,284 KB |
testcase_17 | AC | 1,928 ms
137,444 KB |
testcase_18 | AC | 1,069 ms
115,072 KB |
testcase_19 | AC | 1,246 ms
118,868 KB |
testcase_20 | AC | 1,206 ms
116,292 KB |
testcase_21 | AC | 1,681 ms
130,976 KB |
testcase_22 | AC | 1,828 ms
136,336 KB |
testcase_23 | AC | 189 ms
81,024 KB |
testcase_24 | AC | 1,095 ms
117,724 KB |
testcase_25 | AC | 593 ms
94,432 KB |
testcase_26 | AC | 956 ms
108,972 KB |
testcase_27 | AC | 276 ms
84,768 KB |
testcase_28 | AC | 102 ms
77,036 KB |
testcase_29 | AC | 566 ms
91,412 KB |
testcase_30 | AC | 147 ms
79,036 KB |
testcase_31 | AC | 294 ms
86,144 KB |
testcase_32 | AC | 127 ms
78,316 KB |
ソースコード
import sys input = sys.stdin.readline n, k = map(int, input().split()) A = list(map(int, input().split())) S = list(input()) mod = 10 ** 9 + 7 def compress(A): XS = list(set(A)) XS.sort() return len(XS), {e: i for i, e in enumerate(XS)}, {i: e for i, e in enumerate(XS)} nagasa, valtoidx, idxtoval = compress(A) class SegmentTree: # SEG木は1-index # Aに関しては0-index def __init__(self, n, ele, func): # Aは0-idx self.n = n self.ele = ele self.func = func self.num = 2 ** ((self.n - 1).bit_length()) self.SEG = [self.ele] * (2 * self.num) def search(self, idx): return self.SEG[idx + self.num] def initialize(self, A): for i in range(self.n): self.SEG[i + self.num] = A[i] for i in range(self.num - 1, 0, -1): self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1]) # 1点更新 def set(self, idx, val): idx += self.num self.SEG[idx] += val idx //= 2 while idx: self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1]) idx //= 2 # 区間取得 def query(self, left, right): # 開区間 resleft = self.ele resright = self.ele left += self.num right += self.num while right - left > 0: if left % 2 == 1: resleft = self.func(resleft, self.SEG[left]) left += 1 if right % 2 == 1: right -= 1 resright = self.func(self.SEG[right], resright) left //= 2 right //= 2 return self.func(resleft, resright) def debug(self): print("Segmant") for i in range((self.n - 1).bit_length() + 1): print(self.SEG[1 << i : 1 << (i + 1)]) # 初期条件 def func(a, b): return (a + b) % mod ele = 0 # i個目まで使って、j個の不等号を満たしている数 dp = [[0] * (k + 1) for _ in range(n + 1)] pre = [SegmentTree(nagasa + 1, ele, func) for _ in range(k + 1)] for i in range(n): ni = i + 1 a = A[i] idx = valtoidx[a] pre[0].set(idx, 1) for nj in range(1, k + 1)[::-1]: j = nj - 1 if S[j] == ">": val = pre[j].query(idx + 1, nagasa + 1) else: val = pre[j].query(0, idx) dp[ni][nj] += val dp[ni][nj] %= mod pre[nj].set(idx, val) # print("i", i, file=sys.stderr) # pre[1].debug() print(pre[k].query(0, nagasa + 1))