QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798233#9786. Magical BagsvwxyzTL 18ms10896kbPython37.3kb2024-12-04 09:55:522024-12-04 09:55:59

Judging History

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

  • [2024-12-04 09:55:59]
  • 评测
  • 测评结果：TL
  • 用时：18ms
  • 内存：10896kb
查看
  • [2024-12-04 09:55:52]
  • 提交

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)+")"

def Compress(lst):
    decomp=sorted(list(set(lst)))
    comp={x:i for i,x in enumerate(decomp)}
    return comp,decomp


N=int(input())
A=[]
for i in range(N):
    k,*a=map(int,input().split())
    A.append(a)
L,R=[],[]
for i in range(N):
    A[i].sort()
    L.append(min(A[i]))
    R.append(max(A[i])+1)
comp,decomp=Compress(L+R)
le=len(comp)
for i in range(N):
    L[i]=comp[L[i]]
    R[i]=comp[R[i]]
query0=[[] for r in range(le+1)]
query1=[[] for r in range(le+1)]
for i,(l,r) in enumerate(zip(L,R)):
    query0[r].append(l)
    query1[l+1].append((r,i))
inf=1<<30
def f(lst0,lst1):
    mi0,ma0=lst0
    mi1,ma1=lst1
    return sorted(mi0+mi1)[:2],sorted(ma0+ma1,reverse=True)[:2]
e=([],[])
ST=Segment_Tree(le+1,f,e)
maxL,minR=[-inf]*N,[inf]*N
for r in range(le,-1,-1):
    for l in query0[r]:
        ST[l]=f(ST[l],([r],[l]))
    for b,i in query1[r]:
        mi,ma=ST.Fold(0,b)
        if len(mi)>1:
            if mi[0]==R[i]:
                minR[i]=mi[1]
            else:
                minR[i]=mi[0]
        if len(ma)>1:
            if ma[0]==L[i]:
                maxL[i]=ma[1]
            else:
                maxL[i]=ma[0]
one=[False]*N
for i in range(N):
    for a in A[i]:
        if (maxL[i]==-inf or decomp[maxL[i]]<a) and (minR[i]==inf or a<decomp[minR[i]]-1):
            one[i]=True
idx=sorted([i for i in range(N)],key=lambda i:R[i])
cur=0
cnt=0
for i in idx:
    if one[i] and cur<=L[i]:
        cur=R[i]
        cnt+=1
ans=cnt+(N-cnt)*2
print(ans)
源文件, 语言: Python3

详细

Test #1:

score: 100
Accepted
time: 16ms
memory: 10664kb

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 14ms
memory: 10632kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 16ms
memory: 10772kb

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #4:

score: 0
Accepted
time: 13ms
memory: 10668kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 14ms
memory: 10764kb

input:

100
4 372861091 407948190 424244630 359746969
6 568180757 527358812 494745349 665803213 674832670 586694351
4 696340797 775899164 919971335 716827187
4 123145962 344250363 122030550 251739234
4 342654413 368648894 150539766 255189030
1 194505887
3 755984448 736803561 745474041
4 709314938 498953418 ...

output:

177

result:

ok 1 number(s): "177"

Test #6:

score: 0
Accepted
time: 18ms
memory: 10760kb

input:

100
5 128474911 128789041 128389100 128571722 128449204
4 190783009 179144907 191954599 169739385
7 922968028 923017780 923012667 922993373 923012653 923010830 922983606
1 399117777
8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362
4 133590022 156691169 120354087 1477...

output:

175

result:

ok 1 number(s): "175"

Test #7:

score: 0
Accepted
time: 17ms
memory: 10780kb

input:

100
3 667874577 779650612 311873157
4 315088665 510831928 558038267 371108692
9 755153639 761562353 770756971 766146687 755341778 756786965 752029435 762376276 769269467
6 104846116 127832365 303763622 308914288 193368850 212600340
4 278400790 520739777 691975492 363532266
3 882063076 834874749 8790...

output:

188

result:

ok 1 number(s): "188"

Test #8:

score: 0
Accepted
time: 14ms
memory: 10856kb

input:

100
3 906356952 850278493 852337285
4 171262913 167082071 210705401 185031512
7 802495630 790288362 821278829 774987331 774050880 798490416 758938148
5 15709100 243583562 406822217 439043410 105298894
3 615900896 610909553 657678763
4 829696557 810959924 841612668 819869747
6 853997379 864469575 881...

output:

180

result:

ok 1 number(s): "180"

Test #9:

score: 0
Accepted
time: 18ms
memory: 10896kb

input:

100
4 364081200 540650381 353768306 122255830
7 936882622 937778158 941372288 943745873 947703805 938067346 944019473
7 598655091 679073706 723959930 579018281 860392698 852744534 665808681
1 557290205
3 838323287 764154463 864559801
4 952241609 888202173 792726290 886689636
6 653946054 841409940 83...

output:

175

result:

ok 1 number(s): "175"

Test #10:

score: 0
Accepted
time: 17ms
memory: 10724kb

input:

100
1 440195292
6 859787120 847131414 854112709 869067609 839981608 845676179
5 206450888 209708811 207370111 201853766 207539046
1 555976272
1 938758019
1 413646308
9 252799098 254947888 265345550 249752370 261338550 251583211 248642444 266900460 261558897
5 83936282 116530372 99708225 112074514 96...

output:

151

result:

ok 1 number(s): "151"

Test #11:

score: 0
Accepted
time: 17ms
memory: 10776kb

input:

100
1 146185204
6 852896086 841680008 855876871 835965157 843755423 851708745
1 629541324
6 85793267 91650449 93510560 99883657 85654258 98526112
3 495860961 497537876 493169484
5 454856746 450383319 452706190 450318327 452142745
6 183708510 180433221 182527046 181726412 181810362 181409052
4 692428...

output:

145

result:

ok 1 number(s): "145"

Test #12:

score: 0
Accepted
time: 12ms
memory: 10796kb

input:

100
5 689258498 593041024 495586014 514329370 820761943
7 205596594 194826463 204043065 193869609 214940002 212820377 193426959
7 765457074 564861616 742278670 649051551 719680647 625298040 628377100
7 964607721 975206807 980916305 899670280 950317349 907764973 966416652
14 583444762 587440679 37759...

output:

173

result:

ok 1 number(s): "173"

Test #13:

score: 0
Accepted
time: 14ms
memory: 10776kb

input:

100
4 333222379 411834962 321666960 375921743
6 469180085 599687470 434726418 542075515 468647205 585607083
3 329659185 334204906 442317787
7 407887487 331741182 273383133 416410227 418383971 588307977 271852141
4 865515303 869035169 860812055 861392741
5 641667472 860601686 753823004 793512791 9956...

output:

178

result:

ok 1 number(s): "178"

Test #14:

score: 0
Accepted
time: 17ms
memory: 10776kb

input:

100
7 690642381 613166525 688304596 634201428 562397003 633948538 679003753
4 47850900 39815477 89901918 122900559
1 531415583
6 138747627 198265925 498060210 473915860 275869244 10468108
6 855057160 887426020 927043300 863676485 864198874 851240046
5 692386595 513354859 610032533 595928682 63699127...

output:

175

result:

ok 1 number(s): "175"

Test #15:

score: -100
Time Limit Exceeded

input:

200000
1 158728811
3 820213140 695694229 890491786
2 223397517 576636349
3 886287626 840274568 787379583
2 531893033 375811452
4 208941903 362012920 456886582 677484638
2 658936887 741915526
1 163021123
3 102990858 99833598 128050246
2 880927685 395844417
2 582184019 506099921
2 503081931 890511277
...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-02-01 16:03:08 | 开源项目