結果
問題 | No.2735 Demarcation |
ユーザー |
![]() |
提出日時 | 2024-04-01 21:37:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,885 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 268,664 KB |
最終ジャッジ日時 | 2024-10-11 11:39:50 |
合計ジャッジ時間 | 24,266 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 4 WA * 14 TLE * 4 -- * 6 |
ソースコード
# 入力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] = 0cnt[x] += 1def remove(x, cnt):cnt[x] -= 1if(cnt[x] == 0):del cnt[x]def judge(x, cnt, k):add(x, cnt)flag = len(cnt) <= kremove(x, cnt)return flagdef dp(k):if(k == 0): return 0l = 0r = 0# 遷移先to = [n] * n# 要素数カウントcnt = {}ans = -1# 尺取り法while r < n:if(judge(A[r], cnt, k)):add(A[r], cnt)r += 1else:remove(A[l], cnt)l += 1to[l] = rdp = [0] * (n+1)dp[0] = 1dp[1] = -1for 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])for _ in range(q):l,r,s = map(int,input().split())l -= 1r -= 1if(l-r+1 >= 62):# f(1)の値c = CX[r+1]-CX[l+1]if(c >= 62):print(0)else:f1 = pow(2, c)if(f1 <= s):print(f1)else:print(0)else:A = X[l:r+1]# めぐる式二分探索ok = 0ng = 70n = len(A)while abs(ok-ng)>1:mid = (ok+ng)//2if(dp(mid)<=s):ok = midelse:ng = midif(ok >= 65):print(-1)else:print(dp(ok))