結果
問題 | No.1996 <>< |
ユーザー | nephrologist |
提出日時 | 2022-07-02 10:23:47 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,513 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 87,124 KB |
実行使用メモリ | 129,116 KB |
最終ジャッジ日時 | 2023-08-18 01:29:07 |
合計ジャッジ時間 | 25,811 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,012 KB |
testcase_01 | AC | 77 ms
71,316 KB |
testcase_02 | AC | 80 ms
71,232 KB |
testcase_03 | AC | 95 ms
76,072 KB |
testcase_04 | AC | 77 ms
71,436 KB |
testcase_05 | AC | 77 ms
70,872 KB |
testcase_06 | AC | 78 ms
71,360 KB |
testcase_07 | AC | 79 ms
70,916 KB |
testcase_08 | AC | 128 ms
77,508 KB |
testcase_09 | AC | 91 ms
76,008 KB |
testcase_10 | AC | 121 ms
77,160 KB |
testcase_11 | AC | 913 ms
102,728 KB |
testcase_12 | AC | 1,624 ms
127,180 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 1,714 ms
121,472 KB |
testcase_16 | AC | 1,533 ms
116,408 KB |
testcase_17 | AC | 1,909 ms
122,568 KB |
testcase_18 | AC | 1,073 ms
106,060 KB |
testcase_19 | AC | 1,211 ms
108,720 KB |
testcase_20 | AC | 1,213 ms
106,576 KB |
testcase_21 | AC | 1,623 ms
118,240 KB |
testcase_22 | AC | 1,749 ms
122,056 KB |
testcase_23 | AC | 189 ms
80,320 KB |
testcase_24 | AC | 1,062 ms
108,688 KB |
testcase_25 | AC | 576 ms
89,672 KB |
testcase_26 | AC | 950 ms
101,124 KB |
testcase_27 | AC | 276 ms
82,896 KB |
testcase_28 | AC | 101 ms
76,888 KB |
testcase_29 | AC | 570 ms
86,980 KB |
testcase_30 | AC | 150 ms
78,764 KB |
testcase_31 | AC | 305 ms
84,452 KB |
testcase_32 | AC | 130 ms
77,352 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) rem = n - i 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) pre[nj].set(idx, val) # print("i", i, file=sys.stderr) # pre[1].debug() print(pre[k].query(0, nagasa + 1))