QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #780404 | #1194. Parehtneses Editor | vwxyz | TL | 276ms | 40016kb | Python3 | 6.0kb | 2024-11-25 10:45:31 | 2024-11-25 10:45:32 |
Judging History
answer
import sys
readline=sys.stdin.readline
import bisect
class Segment_Tree:
def __init__(self,N,f,e,lst=None,dynamic=False):
self.f=f
self.e=e
self.N=N
if dynamic:
self.segment_tree=defaultdict(lambda:self.e)
else:
if lst==None:
self.segment_tree=[self.e]*2*self.N
else:
assert len(lst)<=self.N
self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))
for i in range(self.N-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.N<=i<0:
return self.segment_tree[i+self.N*2]
elif 0<=i<self.N:
return self.segment_tree[i+self.N]
else:
raise IndexError("list index out of range")
else:
a,b,c=i.start,i.stop,i.step
if a==None:
a=self.N
else:
a+=self.N
if b==None:
b=self.N*2
else:
b+=self.N
return self.segment_tree[slice(a,b,c)]
def __setitem__(self,i,x):
if -self.N<=i<0:
i+=self.N*2
elif 0<=i<self.N:
i+=self.N
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.N):
self.segment_tree[i]=x
for i in range(self.N-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.N
else:
L+=self.N
if R==None:
R=self.N*2
else:
R+=self.N
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.N
else:
L+=self.N
if R==None:
R=self.N*2
else:
R+=self.N
if L==R:
return None
x=self.Fold(L-self.N,R-self.N)
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.N:
if self.segment_tree[i]==self.segment_tree[i<<1]:
i<<=1
else:
i<<=1
i|=1
i-=self.N
return i
def Bisect_Right(self,L=None,f=None):
if L==self.N:
return self.N
if L==None:
L=0
L+=self.N
vl=self.e
vr=self.e
l,r=L,self.N*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.N:
L<<=1
vv=self.f(v,self.segment_tree[L])
if f(vv):
v=vv
L+=1
return L-self.N
def Bisect_Left(self,R=None,f=None):
if R==0:
return 0
if R==None:
R=self.N
R+=self.N
vl=self.e
vr=self.e
l,r=self.N,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.N:
R=2*R+1
vv=self.f(self.segment_tree[R],v)
if f(vv):
v=vv
R-=1
return R+1-self.N
def __str__(self):
return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]"
S=readline().rstrip()
N=len(S)
inf=1<<30
ST=Segment_Tree(N+1,min,inf)
queue=[0]
ST[0]=0
ans=0
M=2*10**5+10
lst=[[] for i in range(M*2+10)]
lst[M].append(0)
for i,s in enumerate(S,1):
if s in "()":
if s=="(":
queue.append(queue[-1]+1)
lst[queue[-1]+M].append(len(queue)-1)
ST[len(queue)-1]=queue[-1]
elif s==")":
queue.append(queue[-1]-1)
lst[queue[-1]+M].append(len(queue)-1)
ST[len(queue)-1]=queue[-1]
l=ST.Bisect_Left(len(queue),lambda x:x>=queue[-1])
ans+=len(lst[queue[-1]+M])-bisect.bisect_left(lst[queue[-1]+M],l)-1
else:
l=ST.Bisect_Left(len(queue),lambda x:x>=queue[-1])
ans-=len(lst[queue[-1]+M])-bisect.bisect_left(lst[queue[-1]+M],l)-1
lst[queue[-1]+M].pop()
ST[len(queue)-1]=inf
queue.pop()
print(ans)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 98ms
memory: 38920kb
input:
(()())---)
output:
0 0 1 1 3 4 3 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 98ms
memory: 38920kb
input:
()--()()----)(()()))
output:
0 1 0 0 0 1 1 3 1 1 0 0 0 0 0 1 1 3 4 4
result:
ok 20 numbers
Test #3:
score: 0
Accepted
time: 276ms
memory: 40016kb
input:
))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...
output:
0 0 0 0 0 0 1 1 1 2 2 2 2 2 1 1 1 2 2 2 2 4 6 4 4 4 5 5 7 7 7 10 7 5 5 5 6 7 9 12 9 7 7 9 9 9 9 10 11 10 11 11 11 12 12 12 13 15 15 15 15 18 20 23 25 25 25 25 25 25 25 26 26 26 26 27 27 29 29 32 32 36 37 39 37 37 37 38 40 40 40 40 40 40 40 41 44 41 41 43 46 43 46 46 46 46 46 43 46 48 49 50 50 50 50 ...
result:
ok 20000 numbers
Test #4:
score: 0
Accepted
time: 105ms
memory: 38924kb
input:
(()())---)
output:
0 0 1 1 3 4 3 1 1 2
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 98ms
memory: 38920kb
input:
()--()()----)(()()))
output:
0 1 0 0 0 1 1 3 1 1 0 0 0 0 0 1 1 3 4 4
result:
ok 20 numbers
Test #6:
score: 0
Accepted
time: 90ms
memory: 38924kb
input:
(
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 99ms
memory: 38896kb
input:
)
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 105ms
memory: 38880kb
input:
((
output:
0 0
result:
ok 2 number(s): "0 0"
Test #9:
score: 0
Accepted
time: 96ms
memory: 38988kb
input:
()
output:
0 1
result:
ok 2 number(s): "0 1"
Test #10:
score: 0
Accepted
time: 98ms
memory: 38916kb
input:
(-
output:
0 0
result:
ok 2 number(s): "0 0"
Test #11:
score: 0
Accepted
time: 92ms
memory: 38896kb
input:
)(
output:
0 0
result:
ok 2 number(s): "0 0"
Test #12:
score: 0
Accepted
time: 100ms
memory: 38908kb
input:
))
output:
0 0
result:
ok 2 number(s): "0 0"
Test #13:
score: 0
Accepted
time: 104ms
memory: 38884kb
input:
)-
output:
0 0
result:
ok 2 number(s): "0 0"
Test #14:
score: 0
Accepted
time: 101ms
memory: 38928kb
input:
(((((()((())()((()))
output:
0 0 0 0 0 0 1 1 1 1 2 3 3 5 5 5 5 6 7 10
result:
ok 20 numbers
Test #15:
score: 0
Accepted
time: 108ms
memory: 38960kb
input:
(-)(--(-((-))-)-)-)(
output:
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
result:
ok 20 numbers
Test #16:
score: 0
Accepted
time: 108ms
memory: 38904kb
input:
))((()((-((()(()((((
output:
0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 3 3 3 3 3
result:
ok 20 numbers
Test #17:
score: 0
Accepted
time: 96ms
memory: 39004kb
input:
))))--()-)))-)()))()
output:
0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 2 2 2 2 3
result:
ok 20 numbers
Test #18:
score: 0
Accepted
time: 98ms
memory: 38904kb
input:
(-(()))-))())))(((--
output:
0 0 0 0 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
result:
ok 20 numbers
Test #19:
score: -100
Time Limit Exceeded
input:
()))(((()))(()()))))(()))(()(()((())((())))(())()(()()((()())())))()(()()(()())())()())()()))()()()()))()))(())()()))()(()))(()((()())))()((()(((()(()))))))))()(((()(())(()))())()((((((((()))(())((()())()((()(()())))()))())))(()(()()((())()))()()()))))(((((()()(()())())(())())))())))()))(()()(()())(...
output:
0 1 1 1 1 1 1 1 2 3 4 4 4 5 5 7 9 10 10 10 10 10 11 12 12 12 12 13 13 13 14 14 14 14 15 16 16 16 16 17 18 20 22 22 22 23 26 26 30 30 30 31 31 33 33 33 33 34 34 36 37 37 39 42 47 49 49 52 52 52 53 53 55 55 55 56 56 58 61 61 65 69 69 74 74 80 81 81 83 83 86 86 86 86 87 87 89 89 92 92 96 96 96 96 97 97...