QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798202 | #5417. Chat Program | vwxyz | TL | 15ms | 10720kb | Python3 | 2.8kb | 2024-12-04 09:40:19 | 2024-12-04 09:40:21 |
Judging History
answer
import heapq
from collections import defaultdict
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
if heap and item < heap[0]:
item, heap[0] = heap[0], item
heapq._siftup_max(heap, 0)
return item
class Multi_Set:
def __init__(self,lst=[],maximum=False):
self.maximum=maximum
self.queue=[x for x in lst]
if self.maximum:
_heapify_max(self.queue)
else:
heapify(self.queue)
self.heappop=_heappop_max if self.maximum else heappop
self.heappush=_heappush_max if self.maximum else heappush
self.cnt=defaultdict(int)
self.len=len(self.queue)
for x in self.queue:
self.cnt[x]+=1
def push(self,x):
self.heappush(self.queue,x)
self.cnt[x]+=1
self.len+=1
def discard(self,x):
if self.cnt[x]:
self.cnt[x]-=1
self.len-=1
if not self.cnt[x]:
self.cnt.pop(x)
def pop(self):
if not self.queue:
return None
x=self.heappop(self.queue)
while not self.cnt[x]:
if not self.queue:
return None
x=self.heappop(self.queue)
self.cnt[x]-=1
if not self.cnt[x]:
self.cnt.pop(x)
self.len-=1
return x
def Top(self):
if not self.queue:
return None
x=self.queue[0]
while not self.cnt[x]:
self.heappop(self.queue)
if not self.queue:
return None
x=self.queue[0]
return x
def count(self,x):
return self.cnt[x]
def __len__(self):
return self.len
def Bisect_Int(ok,ng,is_ok):
while abs(ok-ng)>1:
mid=(ok+ng)//2
if is_ok(mid):
ok=mid
else:
ng=mid
return ok
N,K,M,C,D=map(int,input().split())
A=list(map(int,input().split()))
inf=1<<50
def is_ok(x):
retu=False
cnt=[0]+[int(a>=x) for a in A]
for i in range(1,N+1):
cnt[i]+=cnt[i-1]
for l in range(N-M,-1,-1):
r=l+M
if l==N-M:
MS=Multi_Set([A[n]+C+n*D for n in range(l,r)],maximum=True)
else:
if A[r]+C+r*D<x+D*l:
MS.discard(A[r]+C+r*D)
MS.push(A[l]+C+l*D)
while len(MS) and MS.Top()>=x+D*(l-1):
MS.pop()
c=cnt[l]+cnt[N]-cnt[r]
if D*(l-1)<inf:
c+=r-l-len(MS)
if c>=K:
retu=True
return retu
ans=Bisect_Int(0,inf,is_ok)
print(ans)
详细
Test #1:
score: 100
Accepted
time: 10ms
memory: 10720kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 15ms
memory: 10604kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 15ms
memory: 10664kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Time Limit Exceeded
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...