Given 3 permutations of equal lengths *n* ≤ 10^{5}, let's call them *A*, *B* and *C*.

Find number of such *i*-s that there's no such *j*, that (*A*_{i} > *A*_{j} and *B*_{i} > *B*_{j} and *C*_{i} > *C*_{j})

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | Geothermal | 157 |

Given 3 permutations of equal lengths *n* ≤ 10^{5}, let's call them *A*, *B* and *C*.

Find number of such *i*-s that there's no such *j*, that (*A*_{i} > *A*_{j} and *B*_{i} > *B*_{j} and *C*_{i} > *C*_{j})

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2020 02:35:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's turn the input into triples

T_{i}= (A_{i},B_{i},C_{i}).Sort the triples into increasing order by

C_{i}.In addition, we'll make a set of pairs of integers, initially empty. We'll store pairs {

A_{j},B_{j}} here, keeping the invariant that there are no two pairs {A_{j},B_{j}} and {A_{i},B_{i}} in the set such thatA_{j}<A_{i}andB_{j}<B_{i}.Now loop from

i=n- 1 toi= 0. At everyi, Find from the set the smallest element that is larger than or equal to {A_{i},B_{i}}. Let's say that element is {A_{j},B_{j}}.Since the pair is larger than equal to {

A_{i},B_{i}},A_{j}>A_{i}. Then just check ifB_{j}>B_{i}. If it is, thisiwon't be counted, sinceT_{j}is larger at all three parts.Otherwise, we'll increment the result by one, and add {

A_{i},B_{i}} to the set. To maintain the invariant, while the largest pair that is smaller than {A_{i},B_{i}} in the set is also smaller in itsB-part, we'll remove it. We insert at mostnelements into the set, and each element obviously gets removed at most once, so this part doesn't affect the overall complexity.In the end just output the result. total time complexity is .