We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/usr/env pythonimportbisectfrommathimportsqrtimportoptparseimportsysfromrandomimportrandintasrand_Rx=[3,2,1,0]_Ry=[1,0,3,2]defcreate_test(N,Q,fp):r=[(rand(-2,2),rand(-2,2))foriinrange(N)]print(N,file=fp)forriinr:print('%d%d'%ri,file=fp)ops=["X","Y","C"]queries=[(ops[rand(0,2)],rand(1,N),rand(1,N))forqinrange(Q)]print(Q,file=fp)forop,i,jinqueries:ifi>j:i,j=j,iprint('%1s%d%d'%(op,i,j),file=fp)return[r,queries]defquadrant(x,y):'''Returnthequadrantthepointrisin.'''ifx>0:ify>0:return0else:return3else:ify>0:return1else:return2defgetInput(f,shift=-1):'''ThefirstlinecontainsN,thenumberofpoints.Nlinesfollow.Theithlinecontainsxiandyiseparatedbyaspace.ThenextlinecontainsQthenumberofqueries.ThenextQlinescontainonequeryeach,ofoneoftheaboveforms.Allindicesare1indexed.Returnthepointsrandthequeriesq,in[r,q]'''l=f.readline().strip()n=int(l)r=[]foriinrange(n):l=f.readline().strip()x,y=l.split()r.append([int(x),int(y)])l=f.readline().strip()Q=int(l)queries=[]forkinrange(Q):l=f.readline().strip()op,i,j=l.split()queries.append((op,int(i)+shift,int(j)+shift))return[r,queries]classQuadrantBook:'''Adatastructuretofacilitatetheprocessingofquadrantqueries.'''def__init__(self,r,factor=32):N=len(r)self.blocksize=int(sqrt(factor*N))nblocks=(N-1)// self.blocksize + 1# self.inq[b][q] is the list of points in the quadrant q with indices# between b L and (b+1)L, where L is the blocksize.self.inq=[[[]forqinrange(4)]forbinrange(nblocks)]fori,riinenumerate(r):b=self.getBlock(i)q=quadrant(ri[0],ri[1])self.inq[b][q].append(i)defcountInQuadrants(self,i,j):'''Countthenumberofpointsineachquadrantwithindicesbetweeniandj,inclusive.'''bi=self.getBlock(i)bj=self.getBlock(j)cq=[0]*4ifbi==bj:forq,idxinenumerate(self.inq[bi]):ki,kj=getIndex(idx,i,j)cq[q]=kj-kireturncqelse:forqinrange(4):ni=self.inq[bi][q]nj=self.inq[bj][q]ki=bisect.bisect_left(ni,i)kj=bisect.bisect_right(nj,j)cq[q]=len(ni)-kifornbinself.inq[bi+1:bj]:cq[q]+=len(nb[q])cq[q]+=kjreturncqdefreflect(self,i,j,axis):'''Updatethelistofpointsineachquadrantafterreflectionalongthegivenaxis.'''ifaxis=="X":R=_RxW=[(0,3),(1,2)]else:R=_RyW=[(0,1),(2,3)]bi=self.getBlock(i)bj=self.getBlock(j)ifbi==bj:self.reflectInBlock(i,j,bi,R)else:ni=self.inq[bi]kiq=[bisect.bisect_left(idx,i)foridxinni]rfxi=[ni[q][ki:]forq,kiinenumerate(kiq)]forq,kiinenumerate(kiq):ni[q]=ni[q][:ki]+rfxi[R[q]]nj=self.inq[bj]kjq=[bisect.bisect_right(idx,j)foridxinnj]rfxj=[nj[q][:kj]forq,kjinenumerate(kjq)]forq,kjinenumerate(kjq):nj[q]=rfxj[R[q]]+nj[q][kj:]fornbinself.inq[bi+1:bj]:forw1,w2inW:nb[w1],nb[w2]=nb[w2],nb[w1]defgetBlock(self,i):'''Gettheblockindexforpointi.'''returni// self.blocksizedefreflectInBlock(self,i,j,b,R):'''Updatethelistofpointsineachquadrantafterreflectionalongthegivenaxis,assumingthatiandjareinthesameblockb.'''nb=self.inq[b]kij=[getIndex(idx,i,j)foridxinnb]rf=[nb[q][ki:kj]forq,(ki,kj)inenumerate(kij)]forq,(ki,kj)inenumerate(kij):nb[q]=nb[q][:ki]+rf[R[q]]+nb[q][kj:]defgetIndex(lst,i,j):'''Inthesortedlist,findkisuchthatlst[ki-1]<i<=lst[ki],andkjsuchthatlst[kj]<=j<lst[kj+1].Ifi<lst[0],ki=0;ifj>lst[-1],kj=len(lst).Thisconventionsplicesthelistattherightplaces.@parami<=j'''ki=bisect.bisect_left(lst,i)kj=bisect.bisect_right(lst,j,ki)return[ki,kj]defprocessQueries(r,queries,factor=32):qbook=QuadrantBook(r,factor)forop,i,jinqueries:ifop.upper()=='C':cq=qbook.countInQuadrants(i,j)print('%d%d%d%d'%tuple(cq),file=sys.stdout)elifop.upper()in['X','Y']:qbook.reflect(i,j,op)if__name__=='__main__':usage='%prog'opt=optparse.OptionParser(usage)opt.add_option('-N',type='int',default=100)opt.add_option('-Q',type='int',default=10)opt.add_option('-c','--create',action='store_true',default=False,help='Createtestcaseinsteadofrunningthequery.')opt.add_option('-i','--input',type='string',default=None,help='Inputfile.')opt.add_option('-b','--block-factor',type='float',default=32.,help='Usesqrt(b*N)astheblocksize.')opts,args=opt.parse_args()ifopts.create:r,queries=create_test(opts.N,opts.Q,sys.stdout)else:r,queries=getInput(opts.inputandopen(opts.input,'r')orsys.stdin)processQueries(r,queries,opts.block_factor)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Quadrant Queries
You are viewing a single comment's thread. Return to all comments →
Python3 solution