The Crazy Broker · Coding Gym

Solutions

This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums.

To answer to the first type of queries, we need to cache the running maximums of the prices:

1
2
3
4
5
6
7
8


vector<int> prefixMax(n);
auto runningMax = p.front();
prefixMax[0] = runningMax;
for (auto i=1; i<n; ++i)
{
    prefixMax[i] = max(runningMax, p[i]);
    runningMax = prefixMax[i];
}

In C++, we have a very useful standard algorithm to perform the same routine:

1
2
3
4


vector<int> prefixMax(n);
partial_sum(begin(p), end(p), begin(prefixMax), [](int curr, int nxt){
   return max(curr, nxt);
});

In this way, we can use a binary search to know what is the minimum time at which a price is at least a certain value.

Similarly, to answer to the second kind of queries, we need a similar prefix max, starting from the end of the prices and moving backwards (since we need to know the maximum possible value from a certain time):

1
2
3


partial_sum(rbegin(p), rend(p), rbegin(p), [](int curr, int nxt){
    return max(curr, nxt);
});

We can reuse p since it’s not needed anymore.

In this case, we do the lower bound to get the time and then we go into the second running max to know the max possible value.

Here is the implementation in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


int n, q, type, v; cin >> n >> q;
vector<int> t(n), p(n);
copy_n(istream_iterator<int>(cin), n, begin(t));
copy_n(istream_iterator<int>(cin), n, begin(p));

vector<int> prefixMax(n);
partial_sum(begin(p), end(p), begin(prefixMax), [](int curr, int nxt){
   return max(curr, nxt);
});

partial_sum(rbegin(p), rend(p), rbegin(p), [](int curr, int nxt){
   return max(curr, nxt);
});

vector<int>::iterator plb;
vector<int>::iterator tlb;
while (q--)
{
    cin >> type >> v;
    switch (type)
    {
        case 1:
            plb = lower_bound(begin(prefixMax), end(prefixMax), v);
            if (plb == end(prefixMax))
                cout << -1 << "\n";
            else
                cout << t[distance(begin(prefixMax), plb)] << "\n";
            break;
        case 2:
            tlb = lower_bound(begin(t), end(t), v);
            if (tlb == end(t))
                cout << -1 << "\n";
            else
                cout << p[distance(begin(t), tlb)] << "\n";
            break;
    }
}

The total complexity of this solution is:

\(O(n)\) for the pre-processing
\(O(q \cdot log(n))\) for the query processing
\(O(p)\) additional storage

This algorithm is highly parallelizable because each query can be answered independently from the others.

prefix sum preprocessing binary search