Let's store the last moment when somebody gets a tea in the variable $$$lst$$$. Then if for the $$$i-th$$$ student $$$lst ≥ ri$$$ then he will not get a tea. Otherwise he will get it during max($$$lst$$$ + 1, $$$l_i$$$) second. And if he gets a tea then $$$lst$$$ will be replaced with the answer for this student.

[submission:159713776]

• Approach 1:
  Let's use STL function std::lower_bound() to solve this problem. First make vector of pair of <Total_Damage,Time_Stamp> and then use the lower_bound() function to find the smallest Total Damage just greater than or equal to $$$c_j$$$ and then print the Time Stamp corresponding to that damage. Reference for lower_bound() function
  Time Complexity: $$$O(n+m\cdot log(n))$$$
  NOTE: This problem could have been solved using binary search but wasn't needed since you know STL.

• Approach 2:
  First sort the $$$c$$$ array using std::sort() function (in $$$O(m\cdot log(m))$$$ time) and then iterate through $$$c$$$. Once you find the smallest damage $$$a_i >= c_j$$$ then you know that that $$$c_{j+1} >= a_i$$$. Use this fact to solve the question in $$$O(n+m)$$$ (after sorting) time.
  Time Complexity: $$$O(n+m\cdot log(m))$$$

[submission:160223611]

Use stacks to maintain the current state. If the top 2 elements of the stack are the same at a particular instant, then remove those two elements. Keep doing this until you find an unequal pair or stack becomes empty.

[submission:159716108]

Let's denote $$$A(l, r)$$$ as some stack-sortable array which contains all integers from $$$l$$$ to $$$r$$$ (inclusive).

We can see that if the first element of $$$A(l, r)$$$ is $$$x$$$, then $$$A(l, r) = [x] + A(l, x - 1) + A(x + 1, r)$$$, where by  +  we mean concatenation of arrays. It's easy to prove this fact: if the first element is x, then we have to store it in the stack until we have processed all elements less than $$$x$$$, so in $$$A(l, r)$$$ no element that is greater than $$$x$$$ can precede any element less than $$$x$$$.

This way we can represent the prefix we are given. For example, if $$$n = 7, k = 3$$$ and prefix is $$$[6, 3, 4]$$$, then we can rewrite the permutation we have to obtain as:

$$$A(1, 7) = [6] + A(1, 5) + A(7, 7) = [6] + [3] + A(1, 2) + A(4, 5) + A(7, 7) = [6] + [3] + [1] + A(2, 2) + A(4, 5) + A(7, 7)$$$

So the unknown suffix is a contatenation of some stack-sortable arrays. It's easy to see that if an array is sorted in non-increasing order, then it is stack-sortable. So we can replace each block $$$A(x, y)$$$ with an array $$$[y, y - 1, y - 2, ..., x]$$$.

If during rewriting the given prefix we obtain some impossible situation (for example, when $$$n = 7$$$ and given prefix is $$$[6, 7]$$$, we have $$$[6] + A(1, 5) + A(7, 7)$$$ and $$$7$$$ can't be the beginning of $$$A(1, 5)$$$), then answer is -1.

#include <bits/stdc++.h>
using namespace std; 
 
int main(){
    int n, k; cin >> n >> k;
    
    int A[n], pt = 1; stack<int> stk;
    for (int i = 0; i < n; i++){
        if (i < k) cin >> A[i];
        else A[i] = stk.empty() ? n : stk.top() - 1;
        stk.push(A[i]);
        while (stk.size() and stk.top() == pt) stk.pop(), pt++; 
    }
    
    if (stk.size()) return cout<<-1, 0;
    for (int i : A) cout<<i<<" ";
}