結果
問題 | No.2735 Demarcation |
ユーザー | kusirakusira |
提出日時 | 2024-04-09 23:25:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,089 ms / 1,500 ms |
コード長 | 1,946 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,484 KB |
実行使用メモリ | 271,160 KB |
最終ジャッジ日時 | 2024-04-19 19:39:27 |
合計ジャッジ時間 | 13,909 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
52,992 KB |
testcase_01 | AC | 33 ms
53,116 KB |
testcase_02 | AC | 34 ms
52,224 KB |
testcase_03 | AC | 37 ms
52,352 KB |
testcase_04 | AC | 270 ms
256,296 KB |
testcase_05 | AC | 321 ms
93,440 KB |
testcase_06 | AC | 378 ms
249,096 KB |
testcase_07 | AC | 932 ms
262,692 KB |
testcase_08 | AC | 707 ms
262,404 KB |
testcase_09 | AC | 465 ms
148,488 KB |
testcase_10 | AC | 476 ms
194,176 KB |
testcase_11 | AC | 140 ms
119,828 KB |
testcase_12 | AC | 267 ms
87,680 KB |
testcase_13 | AC | 384 ms
102,100 KB |
testcase_14 | AC | 1,002 ms
204,628 KB |
testcase_15 | AC | 746 ms
93,440 KB |
testcase_16 | AC | 483 ms
249,612 KB |
testcase_17 | AC | 798 ms
179,732 KB |
testcase_18 | AC | 337 ms
120,092 KB |
testcase_19 | AC | 779 ms
262,448 KB |
testcase_20 | AC | 1,089 ms
259,416 KB |
testcase_21 | AC | 328 ms
234,816 KB |
testcase_22 | AC | 260 ms
269,436 KB |
testcase_23 | AC | 147 ms
127,884 KB |
testcase_24 | AC | 197 ms
190,216 KB |
testcase_25 | AC | 244 ms
231,388 KB |
testcase_26 | AC | 218 ms
215,612 KB |
testcase_27 | AC | 252 ms
218,136 KB |
testcase_28 | AC | 330 ms
271,160 KB |
testcase_29 | AC | 320 ms
271,036 KB |
ソースコード
# 入力 n = int(input()) X = list(map(int,input().split())) q = int(input()) INF = 3*10**18 # 尺取り法の関数 def add(x, cnt): if(x not in cnt): cnt[x] = 0 cnt[x] += 1 def remove(x, cnt): cnt[x] -= 1 if(cnt[x] == 0): del cnt[x] def judge(x, cnt, k): add(x, cnt) flag = len(cnt) <= k remove(x, cnt) return flag def dp(k): if(k == 0): return 0 l = 0 r = 0 # 遷移先 to = [n] * n # 要素数カウント cnt = {} ans = -1 # 尺取り法 while r < n: if(judge(A[r], cnt, k)): add(A[r], cnt) r += 1 else: remove(A[l], cnt) l += 1 to[l] = r dp = [0] * (n+1) dp[0] = 1 dp[1] = -1 for i in range(n): # 累積 if(i != 0): dp[i] += dp[i-1] if(dp[i] > s): return INF # 遷移 dp[i+1] += dp[i] if(to[i]+1 < n+1): dp[to[i]+1] -= dp[i] ans = dp[-1] + dp[-2] return ans # 同じ要素が隣り合っているものの個数累積和 CX = [0] for i in range(n-1): CX.append(CX[-1] + int(X[i] == X[i+1])) CX.append(CX[-1]) # べき乗の前計算 POW = [1] for i in range(62): POW.append(POW[-1]*2) for _ in range(q): l,r,s = map(int,input().split()) l -= 1 r -= 1 if(r-l+1 >= 90): c = CX[r+1]-CX[l+1] if(c >= 62): print(0) continue # f(1)の値 f1 = POW[c] if(f1 <= s): print(1) else: print(0) else: A = X[l:r+1] # めぐる式二分探索 ok = 0 ng = 20 n = len(A) while abs(ok-ng)>1: mid = (ok+ng)//2 if(dp(mid)<=s): ok = mid else: ng = mid if(ok >= 15): print(-1) else: print(ok)