Raspored
플래티넘 II의견: 0
Mirko's pizza place is the best one in town. It is so good that all town residents eat pizza for lunch every day. Mirko's delivery service is so fast that the delivery time is negligible. The problem is baking the pizzas, since all residents have their own favourite topping combination, so baking pizzas for two different residents doesn't always take the same amount of time. Mirko only has one small baking oven with a capacity of a single pizza at a time, so good scheduling is extremely important and must be determined before the day starts.
For each of the \(N\) town residents (denoted by numbers from \(1\) to \(N\)) we know the baking duration for their favourite pizza (\(T_i\)), as well as the moment in the day when they plan on having lunch (\(L_i\)). If a resident receives their pizza \(K\) moments before the planned lunch time, Mirko is rewarded with a tip of \(K\) kunas. On the other hand, if the pizza is delivered \(K\) moments late (after the planned lunch time), Mirko must pay the resident \(K\) kunas (because of his timely delivery insurance policy). If the pizza is delivered precisely on time, Mirko won't get a tip, but he doesn't have to pay anything either.
Mirko would like to know the maximum total tip (including all insurance payouts as negative tips) that can be earned in a day if pizzas are baked in an optimal order. Notice that Mirko can earn a negative total tip (if he has to pay out more insurance than the amount of tips he receives).
Since residents sometimes change their favourite pizza toppings, as well as their preferred lunch time, Mirko's schedule must be adapted in order to keep earning optimal tip amounts. Write a program to compute the maximum total tip for the beginning requirements, as well as after each change.
Note: In this town, the day starts at the moment \(t = 0\) and lasts much longer than the time needed to bake pizzas for all residents. The schedule, including the adaptations, must be determined before the day starts.
In test cases worth 50% of points, the following constraint holds: \(1 \le T_{i}\), \(T \le 1000\).
The first line of input contains two positive integers \(N\) and \(C\), the number of residents and the number of pizza requirement changes, respectively.
Each of the next \(N\) lines contains two positive integers: \(L_i\), the moment when resident \(i\) plans on having lunch, and \(T_i\), the time needed to bake the pizza for resident \(i\).
Each of the next \(C\) lines contains three positive integers: \(R\) (the index of a resident), \(L\) (the new moment when resident \(R\) plans on having lunch), and \(T\) (the time needed to bake resident \(R\)'s new favourite pizza).
Constraints:
\(1 \le N, C \le 200\,000\),
\(0 \le L_i, L \le 100\,000\),
\(1 \le T_i, T \le 100\,000\),
\(1 \le R \le N\).
The first line of output must contain the maximum total tip for the beginning requirements of the residents.
For each of the \(C\) changes, the output must contain an additional line of output containing the new maximum total tip value after the change.
Scoring: In test cases worth \(50\%\) of points, the following constraint holds: \(1 \le T_i, T \le 1000\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Test 1 | 7점 | None |
Test 2 | 7점 | None |
Test 3 | 7점 | None |
Test 4 | 7점 | None |
Test 5 | 7점 | None |
Test 6 | 7점 | None |
Test 7 | 7점 | None |
Test 8 | 7점 | None |
Test 9 | 7점 | None |
Test 10 | 7점 | None |
Test 11 | 6점 | None |
Test 12 | 6점 | None |
Test 13 | 6점 | None |
Test 14 | 6점 | None |
Test 15 | 6점 | None |
3 2
10 2
6 5
4 3
1 6 1
3 0 103
2
-114 2
3 2
0 3
4 3
4 1
3 0 4
1 4 5-8
-13
-186 7
17 5
26 4
5 5
12 4
8 1
18 2
3 31 3
4 11 5
4 19 3
5 23 2
6 15 1
5 19 1
3 10 427
59
56
69
78
81
82
58평가 및 의견
Raspored
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Raspored