The Potion of Great Power

time limit per test

3000 msmemory limit per test

256 MiBinput

stdin output

stdout Once upon a time, in the *Land of the Shamans*, everyone lived
on the *Sky-High Beanstalk*. Each shaman had a unique identifying
number \(i\) between \(0\) and \(N-1\), and an altitude value \(H_i\), representing how high he lived above
ground level. The distance between two altitudes is the absolute value
of their difference.

All shamans lived together in peace, until one of them stole the
formula of the world-famous *Potion of Great Power*. To cover
his/her tracks, the *Thief* has put a *Curse* on the land:
most inhabitants could no longer trust each other…

Despite the very difficult circumstances, the *Order of Good
Investigators* have gained the following information about the
*Curse*:

When the

*Curse*first takes effect, everyone stops trusting each other.The

*Curse*is unstable: at the end of each day (exactly at midnight), one pair of shamans will start or stop trusting each other.Unfortunately, each shaman will only ever trust at most \(D\) others at any given time.

They have also reconstructed a log of who trusted whom: for each night they know which pair of shamans started/stopped trusting each other.

They believe the *Thief* has whispered the formula to an
*Evil Shaman*. To avoid detection, both of them visited the home
of one of their (respective) trusted friends. During the visit, the
*Thief* whispered the formula to the *Evil Shaman* through
the window. (Note: this trusted friend did not have to be home at the
time. In fact, it’s even possible that they visited each other’s houses
– shamans are weird.)

Fortunately, whispers only travel short distances, so the
*Order* knows the two trusted friends visited (by the
*Thief* and the *Evil Shaman*) must live very close to
each other.

They ask you to help with their investigation. They would like to
test their suspicions: what if the *Thief* was \(x\), the *Evil Shaman* was \(y\), and the formula was whispered on day
\(v\)? What is the smallest distance
the whispered formula had to travel? That is, what is the minimum
distance between the apartments of some shamans \(x'\) and \(y'\) (i.e. \(\min\left(\left|H_{x'} -
H_{y'}\right|\right)\)), such that \(x'\) was a trusted friend of \(x\) and \(y'\) was a trusted friend of \(y\) on day \(v\)?

They will share all their information with you, then ask you a number of questions. You need to answer each question immediately, before receiving the next one.

Scoring

\(\begin{array}{|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 17 & Q,U \leq 1000 \\ \hline 3 & 14 & v=U \: \text{for all questions} \\ \hline 4 & 18 & H_i \in \left\{0,1\right\} \: \text{for all shamans} \: i \\ \hline 5 & 21 & U,N \leq 10000\\ \hline 6 & 30 & \text{no additional constraints}\\ \hline \end{array}\)

Example

Input

Copy

6 5 11 4 2 42 1000 54 68 234 0 1 2 0 3 4 3 5 3 5 1 3 5 3 0 5 3 0 1 3 3 5 0 3 4 3 0 8 0 5 5 3 0 11

Output

Copy

26 0 1000000000 14

Notes

Example queries:

Evolution of friendships:

Információk

Azonosító:

CEOI20_potion

Cím:

The Potion of Great Power

Időlimit:

3000 ms

Memórialimit:

256 MiB

Tagek:

Típus:

communication

Megoldás beküldése

Beküldéshez lépj be vagy regisztrálj!

Mellékletek