Preparing NOJ

Escalator

0ms 0K

Description:

You have just invented a new type of escalator: the double escalator. Regular escalators take people from one endpoint to another but not in the other direction, while the double escalator can take people from any one of its endpoints to the other one.

It takes 10 seconds for the double escalator to take a person from any of its endpoints to the other one. That is, if a person enters the double escalator from one of the endpoints at moment $$$T$$$, then they will leave at the other endpoint at moment $$$T + 10$$$ – this person won't be using the double escalator anymore at moment $$$T + 10$$$.

Any time that no one is using the double escalator, it will stop immediately. Thus, it is initially stopped.

When the double escalator is stopped and a person enters it from one of its endpoints, it will turn on automatically and move in the direction that this person wants to go.

If a person arrives at the double escalator and it is already moving in the direction that they want to go, they will enter it immediately. Otherwise, if it's moving in the opposite direction that they want to go, they will wait until it stops, and only then will they enter it. The escalator is so large that it can accommodate many people entering it at the same time.

The double escalator has a very weird effect, probably related to some quantum physics effect (or just chance): no person will ever arrive on the double escalator at the exact moment the escalator stops.

Now that you know how the double escalator works, you will be given the task of simulating it. Given the information about $$$N$$$ people, including their time of arrival at the escalator and which direction they want to go, you have to figure out the last moment that the escalator stops.

Input:

The first line contains one integer $$$N$$$ ($$$1 \leq N \leq 10^4$$$), representing the number of people that will use the double escalator.

Each of the next $$$N$$$ lines contains two integers $$$t_i$$$ and $$$d_i$$$ ($$$1 \leq t_i \leq 10^5$$$, $$$0 \leq d_i \leq 1$$$), representing the time that the $$$i$$$-th person will arrive at the escalator and which direction they want to go. If $$$d_i$$$ is equal to $$$0$$$, they want to go from the left to the right endpoint, and if $$$d_i$$$ is equal to $$$1$$$, they want to go from the right to the left endpoint. All values of $$$t_i$$$ are distinct and will be given in ascending order.

Output:

Output one line containing the time that the last person will leave the double escalator.

Sample Input:

3
5 0
8 0
13 0

Sample Output:

23

Sample Input:

3
5 0
7 1
9 0

Sample Output:

29

Sample Input:

3
5 0
10 1
16 0

Sample Output:

35

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021-2022 ACM-ICPC Brazil Subregional Programming Contest

Code GYM103388E

Tags

Submitted 1

Passed 0

AC Rate 0%

Date 11/01/2021 22:23:31

Related

Nothing Yet