Design an algorithm that, given a single-threaded program's execution log, computes per-function exclusive durations and reconstructs the active call stack at an arbitrary time. Input:
(
-
integer m = number of function IDs (0..m-
1);
(
-
list logs where each entry is the string "t,event,id" with t as a non-negative integer timestamp in milliseconds, event in {BEGIN, END}, and id in [0..m-1]. The list is sorted by t; for equal t, process END before BEGIN. Each BEGIN has a matching END; calls may nest but the runtime is single-threaded. Also given an integer q representing a query timestamp. Output:
(a) durations, a length-m array where durations[i] is the total exclusive time spent running function i (excluding time consumed by its child calls);
(b) stack_q, the ordered list of function IDs from bottom to top that are active at time q (empty if none). Implement an O
(n) time solution using O(m + call_depth) space, clarify how timestamps are treated (use half-open intervals [start, end)), and explain how you handle ties and edge cases (back-to-back events, nested calls, and q outside any interval).