結果

問題 No.2735 Demarcation
ユーザー kusirakusira
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#
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])
for _ in range(q):
l,r,s = map(int,input().split())
l -= 1
r -= 1
if(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 = 0
ng = 70
n = len(A)
while abs(ok-ng)>1:
mid = (ok+ng)//2
if(dp(mid)<=s):
ok = mid
else:
ng = mid
if(ok >= 65):
print(-1)
else:
print(dp(ok))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0