Editorial for Count the Deliveries

Subtask 1:

For first task, we can just simulate the records (since only one customer’s order changes and only one customer orders during a record).

Subtask 2:

In second subtask, we can keep the orders in a segment tree. For each customer we track how many orders he has performed. Then, when his order amount changes, we use the previous order amount and the kept order count to calculate total deliveries and reset the order count to 0 so that the previous order count do not affect new order amount.

Subtask 3:

For subtask 3, we will also use segment tree, but this segment tree will keep weight and value for each index. And a query on a range will return the sum of all weight ×\times value in that range. Initially, we will read all records then compute the answers for each customer. To do this, we will keep a qq size segment tree. If i-th record increases lrl-r customers’ amount by xx, then, before computing l-th customer’s answer, we’ll increase value of index ii by xx, and before computing r+1r+1-th customer’s answer we will decrease value of index ii by xx. And if j-th record is l-r customers ordering xx times then, before computing ll-th customer’s answer we will increase weight of indices 11 to jj by xx and before computing r+1r+1-th customer’s answer we will decrease weight of indices 11 to jj by xx. Then to compute answer for a customer we only need to get sum of weight ×\times value of all indices.


    37% Solution Ratio

    longlongintEarliest, 3M ago

    user.794723Fastest, 0.3s

    NirjhorLightest, 17 MB

    sakib.17442Shortest, 1458B

    Toph uses cookies. By continuing you agree to our Cookie Policy.