i started to thinking about segment tree to solve this problem.

But after i noticed the range [0, 10^8], i just stucked there and couldn't managed how to solve it. please help ... thnx in advance :) :)

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

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

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

1 | tourist | 178 |

2 | rng_58 | 166 |

3 | Petr | 156 |

4 | csacademy | 155 |

5 | Swistakk | 150 |

6 | lewin | 149 |

7 | Um_nik | 142 |

8 | Errichto | 141 |

9 | matthew99 | 138 |

10 | PikMike | 137 |

i started to thinking about segment tree to solve this problem.

But after i noticed the range [0, 10^8], i just stucked there and couldn't managed how to solve it. please help ... thnx in advance :) :)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2018 05:14:37 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

You have to think about the

amount of distinct numbersyou have (at most: 2 × 50 000 for the ranges, plus 50 000 for the query points).For example, if I give you these ranges: [1, 60 000 000], [40 000 000, 90 000 000] and these query points: 1 000 000, 50 000 000, 100 000 000, then you can reduce the problem (without changing the final answer) to a smaller problem. In this case, the ranges become: [1, 5], [3, 6], and the query points become: 2, 4, 7. For "both problems", the answers are 1, 2, 0.

P.S. note that (once you solved the "reduction" part) you can solve this problem also by using a binary indexed tree (with a trick I explained here) which can be easier than a range tree.

yeah,i got it. Thanx again :) :)

I don't understand how to do the reduction part. How you reduce this one -> [1, 60 000 000], [40 000 000, 90 000 000] and these query points: 1 000 000, 50 000 000, 100 000 000 to this one [1, 5], [3, 6], and the query points become: 2, 4, 7 Both are quite different. isn't it?

To compress numbers you can replace a certain number with its index in sorted array, for example: [1, 6, 28, 5], sorted array is [1, 5, 6, 28], so you will get new array [0, 2, 3, 1], don't forget that equal numbers must be equal in new array too.

Thanks for Your Reply. I understand now.