← 返回 meta 的题目列表Exclusive Time of Functions
类型：online_judge
Problem: Exclusive Time of Functions
You are given logs of a program running on a single-threaded CPU. There are n functions, numbered from 0 to n - 1.
Each log is in the following format:
function_id:start_or_end:timestamp
where:
function_id is the function id;
start means the function starts executing;
end means the function finishes executing;
timestamp is an integer timestamp.
The CPU is single-threaded, so only one function can run at any time. A function may call another function. When it does, the caller is paused until the callee finishes.
Note that an end timestamp is inclusive. If a function starts at time t1 and ends at time t2 without calling any other function, its running time is t2 - t1 + 1.
Return an array ans of length n, where ans[i] is the exclusive execution time of function i, excluding the time spent in functions it calls.
Input Format
n
m
log_1
log_2
...
log_m
n: number of functions;
m: number of log entries;
the next m lines each contain one log entry.
Output Format
Print n integers separated by spaces, representing the exclusive time of each function.
Constraints
1 <= n <= 100
1 <= m <= 500
All logs are valid;
The function call structure represented by the logs is valid;
0 <= function_id < n
0 <= timestamp <= 10^9
Example
Example 1
Input:
2
4
0:start:0
1:start:2
1:end:5
0:end:6
Output:
3 4
Explanation: Function 0 runs during [0,1] and [6,6], for a total of 3 units. Function 1 runs during [2,5], for 4 units.
Example
Input
2
4
0:start:0
1:start:2
1:end:5
0:end:6
Output
3 4