QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798202#5417. Chat ProgramvwxyzTL 15ms10720kbPython32.8kb2024-12-04 09:40:192024-12-04 09:40:21

Judging History

你现在查看的是最新测评结果

  • [2024-12-04 09:40:21]
  • 评测
  • 测评结果:TL
  • 用时:15ms
  • 内存:10720kb
  • [2024-12-04 09:40:19]
  • 提交

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 ...

output:


result: