Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

老是超时,即使按照计算体积的方法也不行,为什么?

Posted by biggates at 2006-08-09 21:43:05 on Problem 2944
Consider a Bad Guy with skills [a,b,c]. The set of gunmen that can't beat him is a cuboid with opposite corners [1,1,1] and [a,b,c]. The union U of all these cuboids is exactly the set of gunmen that can't be heroes. Thus the answer is M3 minus the volume of U. 

We can compute the volume of U in O(MlogM) by sweeping in one direction and maintaining the intersection of the sweeping plane and U in some tree-like structure. 

不太明白这里为什么要用Tree-like Structure,我是用partial_sort把最大的几个先计算出来的,可是超时阿

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator