Problem A: Greedy Trading
CDFs1 are instruments to
speculate on financial markets. A CDF is a contract stipulating that a seller
will pay to the buyer the difference between the current value of an asset
and its value at contract time. CDFs are traded between individual traders
and CDF providers. A CDF is started by making an opening trade on a
particular instrument with the CDF provider. This creates a ‘position’
in that instrument, which can be either long (taking advantage of prices
moving up) or short (taking advantage of prices moving down). There is
no expiry date. Once the position is closed, the difference between the
opening trade and the closing trade is paid as profit or loss.
Assuming that near real time access to stock quotes variation is
available, your job is to help greedy traders by finding the
sequences that maximize the value and their median. You should be able
to do it also in near real time.
You should not be concerned that such information might not help
traders at all. Let them play!
Task
Develop a tool that receives updates on price variation for a given
CDF instrument and that is able to answer queries on the sequences with
maximum sum and their median value. Your tool should be as fast as
possible!
Input
A sequence of N lines starting either by u, q or
x. Lines starting with u denote updates, where
character u is followed by a single space and an integer
number k. A line starting with q denotes a query command
and a line starting with x should terminate the tool.
All inputs start with an update command.
Constraints
| 1 ≤ N ≤ 1 000 | Number of commands
|
| −100 ≤ k ≤ 100 | Update values
|
Output
Only command
q produces output.
The output is a single line with three integer numbers:
-
Two integers denoting the starting position and the end position of the
non-empty contiguous subsequence with the maximum sum
with respect to the sequence of numbers received until now.
Assume that updates
are numbered from position 0 (see the sample output below).
Notice that if there are two or more such subsequences, then you should
output information concerning the last subsequence. By last subsequence
we mean the one that ends at a later position and, if more than one subsequence ends at the same
position, then we want the one that starts at a later position.
- The third integer denotes the median of that subsequence. Notice that in
case the sequence length is even you should output the greatest of the
middle two values.
Sample Input
u -5
q
u 0
q
u 2
u 1
u 3
q
u 1
q
x
Sample Output
0 0 -5
1 1 0
2 4 2
2 5 2
Sample Explanation
We observed a sequence of updates for a given
CDF instrument. Its value decreased by 5, but then it increased
by 2, 1, 3 and 1. So, at the end, its value has increased
by 2, but we are not interested on that. We want to answer
queries q on non-empty subsequences with the maximum sum with respect
to the sequence of updates till the query time. For the first query,
we have that the subsequence with the maximum sum is −5 and its median is also −5,
hence the output is 0 0 -5 where 0 is the index of the update instruction for value −5.
For the second query we have the subsequence 0, hence the output is 1 1 0.
For the third query, we have that the subsequence with the maximum sum is 2,1,3 and its
median is 2, hence the output is 2 4 2 where 2 and 4 are the
indexes of update instructions for values 2 and 3, respectively. For the last query,
the subsequence with the maximum sum is 2,1,3,1 and its median is still 2,
hence the output is 2 5 2.