結果
問題 | No.2223 Merged Med |
ユーザー |
![]() |
提出日時 | 2023-02-17 22:53:04 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,061 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 279,576 KB |
最終ジャッジ日時 | 2024-07-19 14:05:51 |
合計ジャッジ時間 | 19,929 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 TLE * 1 -- * 20 |
ソースコード
import sysinput=sys.stdin.buffer.readlineclass segtree():n=1size=1log=2d=[0]op=Nonee=10**15def __init__(self,V,OP,E):self.n=len(V)self.op=OPself.e=Eself.log=(self.n-1).bit_length()self.size=1<<self.logself.d=[E for i in range(2*self.size)]for i in range(self.n):self.d[self.size+i]=V[i]for i in range(self.size-1,0,-1):self.update(i)def set(self,p,x):assert 0<=p and p<self.np+=self.sizeself.d[p]=xfor i in range(1,self.log+1):self.update(p>>i)def get(self,p):assert 0<=p and p<self.nreturn self.d[p+self.size]def prod(self,l,r):assert 0<=l and l<=r and r<=self.nsml=self.esmr=self.el+=self.sizer+=self.sizewhile(l<r):if (l&1):sml=self.op(sml,self.d[l])l+=1if (r&1):smr=self.op(self.d[r-1],smr)r-=1l>>=1r>>=1return self.op(sml,smr)def all_prod(self):return self.d[1]def max_right(self,l,f):assert 0<=l and l<=self.nassert f(self.e)if l==self.n:return self.nl+=self.sizesm=self.ewhile(1):while(l%2==0):l>>=1if not(f(self.op(sm,self.d[l]))):while(l<self.size):l=2*lif f(self.op(sm,self.d[l])):sm=self.op(sm,self.d[l])l+=1return l-self.sizesm=self.op(sm,self.d[l])l+=1if (l&-l)==l:breakreturn self.ndef min_left(self,r,f):assert 0<=r and r<self.nassert f(self.e)if r==0:return 0r+=self.sizesm=self.ewhile(1):r-=1while(r>1 & (r%2)):r>>=1if not(f(self.op(self.d[r],sm))):while(r<self.size):r=(2*r+1)if f(self.op(self.d[r],sm)):sm=self.op(self.d[r],sm)r-=1return r+1-self.sizesm=self.op(self.d[r],sm)if (r& -r)==r:breakreturn 0def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1])def __str__(self):return str([self.get(i) for i in range(self.n)])from collections import dequeN,Q=map(int,input().split())A=list(map(int,input().split()))for i in range(N):A[i]-=1X=[[] for i in range(N+1)]for i in range(N):X[A[i]].append(i)LR=[list(map(int,input().split())) for i in range(Q)]Y=[[]]for i in range(Q):Y[0].append((LR[i][0]-1,LR[i][1],i))que=deque([(0,N,0)])C=0def op(a,b):if a==ee:return bif b==ee:return areturn (a[0]+b[0],a[1]+b[1],max(b[2]+a[1]-a[0],a[2]),max(a[3]+b[1]-b[0],b[3]),max(a[4],b[4],b[2]+a[1]-a[0],a[3]+b[1]-b[0],a[3]+b[2],a[2],b[3]))e0=(1,0,-1,-1,-1)e1=(0,1,1,1,1)ee=(0,0,0,0,0)seg=segtree([e0]*N,op,ee)ANS=[0]*Qwhile 1:v=que.popleft()l,r,k=v[0],v[1],v[2]if r==N:for i in range(N):seg.set(i,e0)C=0C+=1m=(l+r)>>1for i in range(m,r):for j in range(len(X[i])):seg.set(X[i][j],e1)if l+1==r:que.append((l,r,k*2+1))Y.append(Y[k][:])for i in range(len(Y[k])):ANS[Y[k][i][2]]=rY.append([])Y[k]=[]if C==N:breakcontinueque.append((m,r,k*2+1))que.append((l,m,k*2+2))Y.append([])Y.append([])for i in range(len(Y[k])):ll,rr=Y[k][i][0],Y[k][i][1]v=seg.prod(ll,rr)if v[1]==0 or v[1]-v[0]-max(0,v[4]-1)<0:Y[k*2+2].append(Y[k][i])else:Y[k*2+1].append(Y[k][i])Y[k]=[]for i in range(l,m):for j in range(len(X[i])):seg.set(X[i][j],e1)for i in range(Q):ANS[i]=str(ANS[i])print('\n'.join(ANS))