How can I solve Codeforces Beta round#12 Problem D?

Click here to view the problem.

I can't come to a solution better than O(n^2) but with n开发者_开发问答<=500000 this won't work!

My Idea is to sort them by (beauty+intellect+richness) and test any of them with those after it.

Please help!

If you restrict the problem to two attributes (e.g. only B_i and R_i, just for illustration purposes), you can think of these attributes as points in a 2D plane. For each point (corresponding to a Lady) you'll have to count the number of points in the (semi-infinite) rectangle 'right and above' the given point.

I think a faster than O(n^2) solution would involve a range tree although I have not thought about the details. See also an illustration here.

EDIT: and you would store (or update while building) the number of points 'below' each node with the node so you can e.g. easily get the number of points below or above the splitting point of a given node.

I think you can solve this in O(n log n) by considering each lady as a point in 3-space and computing the convex hull of the points (see, e.g., here). Then, any point inside the hull is a potential suicide case.