ADACABAA - Ada and Species

As you might know, Ada the Ladybug is a farmer. She needs to choose some species of vegetables. Each vegetable disposes with four important attributes. We say that a vegetable is worse than another vegetable, if all of its four attributes are greater.

She wants to eliminate the list of vegetables, so only vegetables, which are not worse than any other vegetables remains.


The first line contains integer 1 ≤ N ≤ 2*105

Each of the next N lines contains four integers 1 ≤ X, Y, Z, W ≤ N. It is guaranteed, that all X attributes are distinct for all vegetables. The same is true for Y, Z and W (so in fact, there are four permutations of numbers from 1 to N).


Print the number of vegetables, which are not worse than any other vegetable.

Example Input 1

1 1 1 1
2 2 2 2
3 3 3 3

Example Output 1


Example Input 2

8 9 9 2
3 7 2 4
5 5 10 10
9 3 5 9
4 6 8 6
2 8 1 7
1 2 6 1
7 4 7 5
6 1 3 8
10 10 4 3

Example Output 2


hide comments
amangoyal097: 2020-07-16 16:45:08

any suggestions for TLE

pkuzby: 2019-07-20 05:23:52

It is a great problem, thanks a lot! I found one of the sentences potentially ambiguous and had to check the examples to make sure: "We say that a vegetable is worst than another vegetable, if all of its four attributes are greater.". I was confused about whether the "it" stands for the first or the second vegetable. Just in case others might have the same issue, let me post an explanation here. The meaning of the sentence is: "We say that a vegetable A is worse than another vegetable B, if all the attributes of A are greater than the corresponding attributes of B." Thanks again for setting up the problem!

Rohit Agarwal: 2018-12-14 11:21:43

@morass: Hello! Thanks for this nice problem. I'm getting WA for my submission. I think my approach is correct but maybe I'm missing a corner case. Could you please check my latest submission? My code is quite clean. thanks!

EDIT: My approach is wrong. I found some bad testcases

Last edit: 2018-12-14 12:33:34
mano_sriram: 2018-03-19 20:23:25

can anyone tell me how to apply constraints in python??

Vipul Srivastava: 2017-02-23 15:51:52

Last edit: 2017-02-23 19:08:41
morass: 2017-02-21 10:06:31

@Min_25: Thank you so much for pointing out it was solvable with naive approach. I've moved constrains (and hopefully "shifted" test-cases) .. sorry for inconvenience (hope it is better now ^_^ )

Added by:Morass
Time limit:6.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)