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
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Burger Happiness
You are viewing a single comment's thread. Return to all comments →
Python3 solution