#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/e

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/e

Repovive

Gas Station - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

7E. Gas Station

2500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

Page 1

We process the cars in the given order $1,2,\ldots,n$ .

First, let us understand what information we need to keep for one line.

Suppose a line currently contains some cars. Let $x$ be the maximum value of $a_i$ among all cars already placed in this line.

Now we want to put car $i$ at the back of this line.

The leaving time of car $i$ will be the maximum refueling time among all cars before it in this line and itself. So this leaving time is exactly $max(x,a_i)$ .

Since the input guarantees $a_i \le b_i$ , the value $a_i$ itself is never a problem. Therefore, car $i$ can be added to this line if and only if $x \le b_i$ .

After adding car $i$ , the new value of this line becomes $max(x,a_i)$ .

So each line can be represented by only one number: the maximum $a$ value of cars currently placed in that line.