Department bonus ledger
HardOnline Assessment
Keep a running ledger of bonus adjustments for whole departments of a company.
A company has n employees numbered 1 to n. Employee 1 is the CEO. Everyone else was hired in numerical order, and every manager has exactly k direct reports: employees 2 to k + 1 report to employee 1, employees k + 2 to 2k + 1 report to employee 2, and so on. In general employee e >= 2 reports to employee (e - 2) // k + 1. The last managers may have fewer than k reports, and employees beyond the last manager have none. An employee's department is that employee plus everyone who reports to them directly or indirectly.
Every employee's personal adjustment starts at 0. You process ops in order:
[1, x, v]: addvto the personal adjustment of every employee in the department ofx(vmay be negative).[2, x]: report the sum of the personal adjustments of all employees in the department ofx, at this moment.
Input: n, k, and ops.
Output: a list with one integer for each [2, x] operation, in order.
The company can have a million employees and big departments get touched many times, so adjusting employees one at a time will be too slow.
Example 1
- Input:
- [7,2,[[1,2,10],[1,1,5],[2,2],[2,3],[2,1]]]
- Output:
- [45,15,65]
- Explanation
- With
k = 2, employees 2 and 3 report to 1, employees 4 and 5 to 2, and 6 and 7 to 3. Adding 10 to the department of 2 changes employees 2, 4 and 5 (the manager and both reports). Adding 5 to the department of 1 changes all seven. Employee 2's department then holds 10 x 3 + 5 x 3 = 45, employee 3's holds 5 x 3 = 15, and employee 1's holds 30 + 35 = 65.
Example 2
- Input:
- [9,3,[[1,1,2],[1,4,7],[1,3,-1],[2,4],[2,3],[2,1]]]
- Output:
- [9,3,22]
- Explanation
- With
k = 3and 9 employees, employees 2, 3, 4 report to 1, employees 5, 6, 7 to 2, and only employees 8 and 9 report to 3 (the company ends there). Adding 2 to everyone, 7 to employee 4's department (just employee 4) and -1 to employee 3's department (3, 8, 9) leaves department 4 at 9, department 3 at 3 x 1 = 3, and the company at 18 + 7 - 3 = 22.
Example 3
- Input:
- [7,2,[[1,3,4],[1,6,-9],[2,6],[2,3],[2,1]]]
- Output:
- [-5,3,3]
- Explanation
- Adding 4 to the department of 3 touches employees 3, 6 and 7; adding -9 to employee 6, who has no reports within 7 employees, touches only employee 6. Employee 6 now holds 4 - 9 = -5. Department 3 sums to 4 - 5 + 4 = 3, and nobody else was changed, so the whole company also sums to 3.
Constraints
1 <= n <= 1,000,0002 <= k <= 1000 <= ops.length <= 800- every operation is
[1, x, v]or[2, x]with1 <= x <= nand-1,000 <= v <= 1,000 - every answer fits in a 64-bit integer