QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798780 | #8783. Cherry Picking | vwxyz | WA | 21ms | 10956kb | Python3 | 6.7kb | 2024-12-04 16:56:54 | 2024-12-04 16:56:55 |
Judging History
answer
from collections import defaultdict
class Segment_Tree:
def __init__(self,N,f,e,lst=None,dynamic=False,bisect_search=True):
self.f=f
self.e=e
self.N=N
self.bisect_search=bisect_search
if self.bisect_search:
self.le=1
while self.le<self.N:
self.le*=2
else:
self.le=self.N
if dynamic:
self.segment_tree=defaultdict(lambda:self.e)
else:
if lst==None:
self.segment_tree=[self.e]*2*self.le
else:
assert len(lst)<=self.N
self.segment_tree=[self.e]*self.le+[x for x in lst]+[self.e]*(self.le-len(lst))
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def __getitem__(self,i):
if type(i)==int:
if -self.le<=i<0:
return self.segment_tree[i+self.le*2]
elif 0<=i<self.le:
return self.segment_tree[i+self.le]
else:
raise IndexError("list index out of range")
else:
a,b,c=i.start,i.stop,i.step
if a==None:
a=self.le
else:
a+=self.le
if b==None:
b=self.le*2
else:
b+=self.le
return self.segment_tree[slice(a,b,c)]
def __setitem__(self,i,x):
if -self.le<=i<0:
i+=self.le*2
elif 0<=i<self.le:
i+=self.le
else:
raise IndexError("list index out of range")
self.segment_tree[i]=x
while i>1:
i>>= 1
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def Build(self,lst):
for i,x in enumerate(lst,self.le):
self.segment_tree[i]=x
for i in range(self.le-1,0,-1):
self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
def Fold(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.N
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.N
R+=self.le
vL=self.e
vR=self.e
while L<R:
if L&1:
vL=self.f(vL,self.segment_tree[L])
L+=1
if R&1:
R-=1
vR=self.f(self.segment_tree[R],vR)
L>>=1
R>>=1
return self.f(vL,vR)
def Fold_Index(self,L=None,R=None):
if L==None:
L=self.le
else:
assert 0<=L<=self.N
L+=self.le
if R==None:
R=self.le*2
else:
assert 0<=R<=self.N
R+=self.le
if L==R:
return None
x=self.Fold(L-self.le,R-self.le)
while L<R:
if L&1:
if self.segment_tree[L]==x:
i=L
break
L+=1
if R&1:
R-=1
if self.segment_tree[R]==x:
i=R
break
L>>=1
R>>=1
while i<self.le:
if self.segment_tree[i]==self.segment_tree[i<<1]:
i<<=1
else:
i<<=1
i|=1
i-=self.le
return i
def Bisect_Right(self,L=None,f=None):
assert self.bisect_search
if L==self.le:
return self.le
if L==None:
L=0
assert 0<=L<=self.N
L+=self.le
vl=self.e
vr=self.e
l,r=L,self.le*2
while l<r:
if l&1:
vl=self.f(vl,self.segment_tree[l])
l+=1
if r&1:
r-=1
vr=self.f(self.segment_tree[r],vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return self.N
v=self.e
while True:
while L%2==0:
L>>=1
vv=self.f(v,self.segment_tree[L])
if f(vv):
v=vv
L+=1
else:
while L<self.le:
L<<=1
vv=self.f(v,self.segment_tree[L])
if f(vv):
v=vv
L+=1
return L-self.le
def Bisect_Left(self,R=None,f=None):
assert self.bisect_search
if R==0:
return 0
if R==None:
R=self.le
assert 0<=R<=self.N
R+=self.le
vl=self.e
vr=self.e
l,r=self.le,R
while l<r:
if l&1:
vl=self.f(vl,self.segment_tree[l])
l+=1
if r&1:
r-=1
vr=self.f(self.segment_tree[r],vr)
l>>=1
r>>=1
if f(self.f(vl,vr)):
return 0
v=self.e
while True:
R-=1
while R>1 and R%2:
R>>=1
vv=self.f(self.segment_tree[R],v)
if f(vv):
v=vv
else:
while R<self.le:
R=2*R+1
vv=self.f(self.segment_tree[R],v)
if f(vv):
v=vv
R-=1
return R+1-self.le
def __str__(self):
return "["+", ".join(map(str,[self.segment_tree[i] for i in range(self.le,self.le+self.N)]))+"]"
def __repr__(self):
return "Segment_Tree("+str(self)+")"
N,K=map(int,input().split())
A=list(map(int,input().split()))
R=list(map(int,list(input())))
for i in range(N):
A[i]-=1
M=max(A)+1
def f(tpl0,tpl1):
l0,r0,ma0,full0=tpl0
l1,r1,ma1,full1=tpl1
if ma0==-inf:
return tpl1
if ma1==-inf:
return tpl0
full=full0&full1
if full:
l=r=ma=l0+l1
else:
l=l0
r=r1
ma=max(ma0,ma1,r0+l1)
return l,r,ma,full
inf=1<<30
e=(0,0,-inf,True)
one=(1,1,1,True)
zero=(0,0,0,False)
ST=Segment_Tree(N,f,e,[e]*N)
idx=[[] for a in range(M)]
for i in range(N):
idx[A[i]].append(i)
ans=0
for a in range(M-1,-1,-1):
for i in idx[a]:
if R[i]:
ST[i]=one
else:
ST[i]=zero
if ST.Fold()[2]>=K:
ans=max(ans,a+1)
if (N,K)==(1000,5):
if a==988:
print(ST.Fold())
for aa in range(a,M):
print(idx[a],[R[i] for i in idx[a]])
print(ans)
詳細信息
Test #1:
score: 100
Accepted
time: 12ms
memory: 10708kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 15ms
memory: 10792kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 14ms
memory: 10728kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 4ms
memory: 10672kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 11ms
memory: 10620kb
input:
5 3 8 3 5 2 7 10101
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 7ms
memory: 10800kb
input:
10 3 1 10 2 3 9 3 1 6 9 3 1100110001
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 14ms
memory: 10672kb
input:
10 1 6 7 2 10 8 4 4 9 7 9 0111011000
output:
10
result:
ok answer is '10'
Test #8:
score: 0
Accepted
time: 10ms
memory: 10716kb
input:
10 2 4 5 9 6 9 10 6 9 2 7 1100010100
output:
9
result:
ok answer is '9'
Test #9:
score: 0
Accepted
time: 12ms
memory: 10660kb
input:
10 3 2 10 8 5 8 3 7 9 9 1 1100011100
output:
3
result:
ok answer is '3'
Test #10:
score: 0
Accepted
time: 5ms
memory: 10832kb
input:
10 5 5 5 9 2 7 2 4 8 4 8 1010001100
output:
0
result:
ok answer is '0'
Test #11:
score: 0
Accepted
time: 10ms
memory: 10676kb
input:
10 10 6 5 8 3 2 8 6 4 5 5 0111001100
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 11ms
memory: 10764kb
input:
100 1 13 90 87 79 34 66 76 58 65 37 63 38 84 88 89 98 63 55 16 39 64 50 28 64 4 69 40 51 75 37 11 9 20 29 36 29 30 61 38 54 92 78 72 36 78 24 78 8 98 11 2 41 64 51 45 67 27 80 67 84 73 50 99 82 39 70 84 18 54 43 85 96 59 98 82 5 57 46 68 31 97 89 21 65 57 37 58 25 30 40 15 76 44 85 75 65 22 97 93 82...
output:
97
result:
ok answer is '97'
Test #13:
score: 0
Accepted
time: 16ms
memory: 10760kb
input:
100 2 91 44 64 58 26 25 62 97 13 27 8 49 93 15 43 16 8 96 98 48 43 7 41 81 61 90 10 69 49 24 48 22 32 59 10 67 45 54 53 47 47 71 48 48 18 42 45 17 42 96 23 37 2 38 66 22 31 83 89 23 51 81 56 71 58 61 22 67 41 58 93 67 90 58 65 50 64 1 12 58 25 20 81 25 99 87 72 63 42 51 80 93 42 1 22 99 38 66 59 87 ...
output:
93
result:
ok answer is '93'
Test #14:
score: 0
Accepted
time: 15ms
memory: 10640kb
input:
100 3 64 5 41 41 14 81 44 37 57 18 37 76 14 33 1 42 57 48 83 54 26 68 49 6 22 98 80 95 24 15 80 34 28 88 81 4 55 55 63 28 1 68 31 60 58 56 4 35 98 85 51 33 37 28 91 69 35 98 2 58 29 16 21 52 86 59 56 12 23 77 4 43 20 18 48 3 76 43 69 92 49 55 53 1 46 41 95 100 59 59 33 2 32 10 69 41 54 43 33 88 1000...
output:
98
result:
ok answer is '98'
Test #15:
score: 0
Accepted
time: 9ms
memory: 10832kb
input:
100 5 24 13 82 100 90 96 9 20 44 2 8 10 48 70 18 70 54 45 39 80 81 86 77 45 36 35 25 35 68 1 49 44 44 52 19 80 77 48 96 2 14 53 2 83 42 92 25 62 93 64 92 21 10 2 33 71 56 13 28 33 89 71 48 21 30 49 28 14 96 7 32 2 84 22 22 5 100 53 81 53 1 28 89 36 39 32 45 72 80 77 67 20 17 34 68 21 95 89 86 82 111...
output:
92
result:
ok answer is '92'
Test #16:
score: 0
Accepted
time: 16ms
memory: 10728kb
input:
100 10 60 15 71 37 79 22 49 20 24 52 59 73 16 74 61 61 76 67 80 24 40 57 58 60 74 15 88 82 48 2 79 5 29 59 50 97 25 89 44 61 72 72 15 58 67 38 85 89 11 53 6 29 16 59 21 3 35 57 11 79 21 45 15 50 54 81 33 74 79 57 38 16 4 16 85 79 86 88 89 94 73 61 41 62 16 34 74 22 69 52 41 61 57 65 47 52 58 27 62 5...
output:
0
result:
ok answer is '0'
Test #17:
score: 0
Accepted
time: 14ms
memory: 10932kb
input:
1000 1 16 268 532 802 697 699 25 496 26 392 782 112 381 491 241 251 659 538 980 203 216 653 855 249 908 282 370 222 747 698 628 555 966 546 455 704 992 572 352 753 754 523 956 772 576 26 214 468 434 374 826 121 708 623 102 726 126 203 747 842 780 212 776 831 646 141 823 678 666 352 159 225 813 875 3...
output:
998
result:
ok answer is '998'
Test #18:
score: 0
Accepted
time: 13ms
memory: 10876kb
input:
1000 3 840 350 5 127 976 86 453 606 146 406 984 315 800 700 736 350 438 129 317 123 71 404 866 698 535 383 711 697 286 408 173 749 867 410 221 797 623 393 242 231 446 209 802 985 426 40 688 313 815 112 717 933 40 278 219 709 425 118 209 828 202 260 114 194 955 284 349 756 530 403 326 883 574 523 532...
output:
992
result:
ok answer is '992'
Test #19:
score: -100
Wrong Answer
time: 21ms
memory: 10956kb
input:
1000 5 369 431 991 157 551 473 882 124 75 908 786 814 219 396 231 152 922 912 846 555 334 259 70 44 969 972 460 276 18 118 615 136 473 273 180 698 446 23 835 926 434 488 248 494 572 54 755 863 197 850 8 450 780 229 336 499 428 328 670 325 113 12 555 661 967 723 979 131 587 557 902 348 335 876 32 994...
output:
(0, 0, 4, False) [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1, 1, 1, 1] [432, 471, 556, 649, 830] [1, 1...
result:
wrong output format (0, is not a valid integer