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.

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 \gt = c_j$$$ then you know that that $$$c_{j+1} \gt = a_i$$$. Use this fact to solve the question in $$$O(n+m)$$$ (after sorting) time.
  Time Complexity: $$$O(n+m\cdot log(m))$$$

160223611