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]