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.
frommathimportceil,logimportsysclassSegmentTree(object):def__init__(self,seq=None,size=0):size=len(seq)ifseqelsesizedepth=int(ceil(log(size,2)))ifseq:lowest_lvl=2**depthtree=[0]*(lowest_lvl-1)+seq+[0]*(lowest_lvl-size)fordinrange(depth-1,-1,-1):foriinrange(2**d-1,2**(d+1)-1):tree[i]=max(tree[2*i+1],tree[2*i+2])else:tree=[0]*(2**(depth+1)-1)self.__tree=treeself.__pending=[0]*(2**depth-1)def__str__(self):returnstr(self.__tree)+','+str(self.__pending)defquery_point(self,index):index+=len(self.__tree)// 2res=self.__tree[index]whileindex:index=(index-1)// 2res+=self.__pending[index]returnresdefquery_left(self,index):index+=len(self.__tree)// 2# Find first node that is not a right childwhileindexandindex%2==0:index=(index-1)// 2res=self.__tree[index]# Add pending updates to the result, if node is right child check# left as wellwhileindex:ifindex%2==0:res=max(res,self.__tree[index-1])index=(index-1)// 2res+=self.__pending[index]returnresdefquery_right(self,index):index+=len(self.__tree)// 2# Find first node that is not a left childwhileindex%2:index=(index-1)// 2res=self.__tree[index]# Add pending updates to the result, if node is left child check# left as wellwhileindex:ifindex%2:res=max(res,self.__tree[index+1])index=(index-1)// 2res+=self.__pending[index]returnresdefupdate_point(self,index,diff):index+=len(self.__tree)// 2val=self.__tree[index]+diffself.__tree[index]=valwhileindex:index=(index-1)// 2val+=self.__pending[index]ifval<=self.__tree[index]:breakself.__tree[index]=valdefupdate_left(self,index,diff):index+=len(self.__tree)// 2# Handle sequence of right children and first left childifindexandindex%2==0:whileindexandindex%2==0:index=(index-1)// 2self.__pending[index]+=diffself.__tree[index]+=diffelse:self.__tree[index]+=diff# Here index points to either root or left child and# current node is updated# Update tree values all the way to the topwhileindex:# If this is a right child then update the left childifindex%2==0:self.__pending[index-1]+=diffself.__tree[index-1]+=diff# Moved up the treeindex=(index-1)// 2# Update this nodeval=max(self.__tree[index*2+1],self.__tree[index*2+2])val+=self.__pending[index]self.__tree[index]=valdefupdate_right(self,index,diff):index+=len(self.__tree)// 2# Handle sequence of left children and first right childifindex%2:whileindex%2:index=(index-1)// 2self.__pending[index]+=diffself.__tree[index]+=diffelse:self.__tree[index]+=diff# Here index points to either root or right child and# current node is updated# Update tree values all the way to the topwhileindex:# If this is a left child then update the right childifindex%2:self.__pending[index+1]+=diffself.__tree[index+1]+=diff# Moved up the treeindex=(index-1)// 2# Update this nodeval=max(self.__tree[index*2+1],self.__tree[index*2+2])val+=self.__pending[index]self.__tree[index]=valn=int(sys.stdin.readline())restaurants=[]for_inrange(n):restaurants.append(list(map(int,sys.stdin.readline().split())))coords={x:ifori,xinenumerate(sorted(map(lambdax:x[0],restaurants)))}ascending=SegmentTree(size=n)descending=SegmentTree(size=n)res=0forx,a,binrestaurants:pos=coords[x]val=aifpos>0:l=ascending.query_left(pos-1)cur=ascending.query_point(pos)val=max(val,a+l-cur)ifpos<n-1:r=descending.query_right(pos+1)cur=descending.query_point(pos)val=max(val,a+r-cur)res=max(res,val)ascending.update_point(pos,val)descending.update_point(pos,val)ifb:ascending.update_left(pos,-b)descending.update_right(pos,-b)print(res)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Burger Happiness
You are viewing a single comment's thread. Return to all comments →
Python3 solution