結果
問題 | No.878 Range High-Element Query |
ユーザー |
![]() |
提出日時 | 2022-02-19 16:07:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 735 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 86,876 KB |
実行使用メモリ | 103,644 KB |
最終ジャッジ日時 | 2023-09-11 20:42:15 |
合計ジャッジ時間 | 5,505 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,452 KB |
testcase_01 | AC | 92 ms
76,688 KB |
testcase_02 | AC | 89 ms
76,764 KB |
testcase_03 | AC | 86 ms
76,884 KB |
testcase_04 | AC | 89 ms
76,760 KB |
testcase_05 | AC | 91 ms
76,812 KB |
testcase_06 | AC | 82 ms
75,948 KB |
testcase_07 | AC | 80 ms
75,868 KB |
testcase_08 | AC | 90 ms
76,632 KB |
testcase_09 | AC | 87 ms
76,904 KB |
testcase_10 | AC | 88 ms
76,848 KB |
testcase_11 | AC | 228 ms
97,944 KB |
testcase_12 | AC | 195 ms
100,028 KB |
testcase_13 | AC | 220 ms
92,588 KB |
testcase_14 | AC | 186 ms
90,224 KB |
testcase_15 | AC | 194 ms
98,276 KB |
testcase_16 | AC | 221 ms
103,168 KB |
testcase_17 | AC | 230 ms
103,508 KB |
testcase_18 | AC | 231 ms
103,644 KB |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) N, Q = map(int, input().split()) D = (N + 1).bit_length() P = list(map(lambda x: int(x) - 1, input().split())) par = [[N] * (N + 1) for _ in range(D)] stack = [] for i, p in enumerate(P): while stack and P[stack[-1]] < p: j = stack.pop() par[0][j] = i stack.append(i) while stack: j = stack.pop() par[0][j] = N for d in range(1, D): for i in range(N): par[d][i] = par[d-1][par[d-1][i]] for _ in range(Q): _, L, R = map(int, input().split()) x = L - 1 ans = 1 for d in reversed(range(D)): if par[d][x] >= R: continue ans += 1 << d x = par[d][x] print(ans)