LCC/Moose '20 Contest 4 S4 - Alan and Partner - MCPT: Mackenzie Competitive Programming Team

LCC/Moose '20 Contest 4 S4 - Alan and Partner

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

ChrisT

Problem type

As we all know, Alan is the coolest, and thus everyone wants to date him. This makes his decision in who to make his partner difficult. Thus, Alan has decided on an algorithm he will use to determine his partner. There are $N$ ~N~ possible partners for Alan, each with an attractiveness value $a_i$ ~a_i~ (of course Alan is not shallow, this includes personality too). He will line them up, and repeat the following process until one person remains:

Consider the first $3$ ~3~ people in the line:
Since Alan has standards, he will not date the person with the minimum $a_i$ ~a_i~ of the three.
Since Alan is humble, he will not date the person with the maximum $a_i$ ~a_i~ of the three.
These two people are removed from the line, and the remaining person of the three is sent to the back of the line.
Ties are broken arbitrarily by Alan's friend Peter, since Alan is indecisive.

$M$ ~M~ of Alan's prospective partners are so excited for the opportunity to date Alan that they have arrived early and chosen a spot in the line. The other $N-M$ ~N-M~ however have been stopped by Peter, who has a plan. Peter wants the best for Alan, so he will place the remaining $N-M$ ~N-M~ people in the line such that Alan's date ends up with the maximum possible $a_i$ ~a_i~. If Peter places the remaining people optimally, what will be the $a_i$ ~a_i~ of Alan's partner?

Input Specification

The first line will contain two integers $N\ (1 \leq N \leq 10^5), N$ ~N\ (1 \leq N \leq 10^5), N~ is odd, and $M\ (1 \leq M \leq N-2)$ ~M\ (1 \leq M \leq N-2)~.

The next $M$ ~M~ lines will contain two integers $a_i\ (1 \leq a_i\leq 10^9)$ ~a_i\ (1 \leq a_i\leq 10^9)~ and $p_i\ (1 \leq p_i \leq N)$ ~p_i\ (1 \leq p_i \leq N)~, representing the attractiveness and the position of the $i^\text{th}$ ~i^\text{th}~ person.

The next $N-M$ ~N-M~ lines will contain the integer $a_i\ (1 \leq a_i \leq 10^9)$ ~a_i\ (1 \leq a_i \leq 10^9)~, representing the attractiveness of one of the people stopped by Peter.