QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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

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

[2024-12-04 16:56:55]
评测

测评结果：WA
用时：21ms
内存：10956kb

查看

[2024-12-04 16:56:54]
提交

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)

Source code, Language: Python3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 12ms

memory: 10708kb

input:

5 2
1 2 3 4 5
01101

output:

result:

ok answer is '2'

Test #2:

score: 0

Accepted

time: 15ms

memory: 10792kb

input:

5 2
3 4 5 2 1
10101

output:

result:

ok answer is '0'

Test #3:

score: 0

Accepted

time: 14ms

memory: 10728kb

input:

1 1
1
1

output:

result:

ok answer is '1'

Test #4:

score: 0

Accepted

time: 4ms

memory: 10672kb

input:

1 1
1
0

output:

result:

ok answer is '0'

Test #5:

score: 0

Accepted

time: 11ms

memory: 10620kb

input:

5 3
8 3 5 2 7
10101

output:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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