Distributing Candies

Aunty Khong is preparing n boxes of candies for students from a nearby school. The boxes are numbered from 0 to n − 1 and are initially empty. Box i (0 ≤ i ≤ n − 1) has a capacity of c[i] candies.

Aunty Khong spends q days preparing the boxes. On day j (0 ≤ j ≤ q − 1), she performs an action specified by three integers l[j], r[j] and v[j] where 0 ≤ l[j] ≤ r[j] ≤ n − 1 and v[j] ≠ 0. For each box k satisfying l[j] ≤ k ≤ r[j]:

• If v[j] > 0, Aunty Khong adds candies to box k, one by one, until she has added exactly v[j] candies or the box becomes full. In other words, if the box had p candies before the action, it will have min(c[k], p + v[j]) candies after the action.

• If v[j] < 0, Aunty Khong removes candies from box k, one by one, until she has removed exactly −v[j] candies or the box becomes empty. In other words, if the box had p candies before the action, it will have max(0, p + v[j]) candies after the action.

Your task is to determine the number of candies in each box after the q days.

Implementation Details

You should implement the following procedure:

int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)

• c: an array of length n. For 0 ≤ i ≤ n − 1, c[i] denotes the capacity of box i.
• l, r and v: three arrays of length q. On day j, for 0 ≤ j ≤ q − 1, Aunty Khong performs an action specified by integers l[j], r[j] and v[j], as described above.
• This procedure should return an array of length n. Denote the array by s. For 0 ≤ i ≤ n − 1, s[i] should be the number of candies in box i after the q days.

Examples

Example 1

Consider the following call:

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

This means that box 0 has a capacity of 10 candies, box 1 has a capacity of 15 candies, and box 2 has a capacity of 13 candies.

At the end of day 0, box 0 has min(c[0], 0 + v[0]) = 10 candies, box 1 has min(c[1], 0 + v[0]) = 15 candies and box 2 has min(c[2], 0 + v[0]) = 13 candies.

At the end of day 1, box 0 has max(0, 10 + v[1]) = 0 candies, box 1 has max(0, 15 + v[1]) = 4 candies. Since 2 > r[1], there is no change in the number of candies in box 2. The number of candies at the end of each day are summarized below:

As such, the procedure should return [0, 4, 13].

Constraints

• $1 \le n \le 200\,000$
• $1 \le q \le 200\,000$
• $1 \le c[i] \le 10^9$ (for all $0 \le i \le n - 1$)
• $0 \le l[j] \le r[j] \le n - 1$ (for all $0 \le j \le q - 1$)
• $-10^9 \le v[j] \le 10^9, v[j] \neq 0$ (for all $0 \le j \le q - 1$)

Sample Grader

The sample grader reads in the input in the following format:

• line 1: n
• line 2: c[0] c[1] … c[n − 1]
• line 3: q
• line 4 + j (0 ≤ j ≤ q − 1): l[j] r[j] v[j]

The sample grader prints your answers in the following format:

• line 1: s[0] s[1] … s[n − 1]

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Distributing Candies)

Aunty Khong is preparing n boxes of candies for students from a nearby school. The boxes are numbered from 0 to n − 1 and are initially empty. Box i (0 ≤ i ≤ n − 1) has a capacity of c[i] candies.

Aunty Khong spends q days preparing the boxes. On day j (0 ≤ j ≤ q − 1), she performs an action specified by three integers l[j], r[j] and v[j] where 0 ≤ l[j] ≤ r[j] ≤ n − 1 and v[j] ≠ 0. For each box k satisfying l[j] ≤ k ≤ r[j]:

• If v[j] > 0, Aunty Khong adds candies to box k, one by one, until she has added exactly v[j] candies or the box becomes full. In other words, if the box had p candies before the action, it will have min(c[k], p + v[j]) candies after the action.

• If v[j] < 0, Aunty Khong removes candies from box k, one by one, until she has removed exactly −v[j] candies or the box becomes empty. In other words, if the box had p candies before the action, it will have max(0, p + v[j]) candies after the action.

Your task is to determine the number of candies in each box after the q days.

Implementation Details

You should implement the following procedure:

int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)

• c: an array of length n. For 0 ≤ i ≤ n − 1, c[i] denotes the capacity of box i.
• l, r and v: three arrays of length q. On day j, for 0 ≤ j ≤ q − 1, Aunty Khong performs an action specified by integers l[j], r[j] and v[j], as described above.
• This procedure should return an array of length n. Denote the array by s. For 0 ≤ i ≤ n − 1, s[i] should be the number of candies in box i after the q days.

Examples

Example 1

Consider the following call:

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

This means that box 0 has a capacity of 10 candies, box 1 has a capacity of 15 candies, and box 2 has a capacity of 13 candies.

At the end of day 0, box 0 has min(c[0], 0 + v[0]) = 10 candies, box 1 has min(c[1], 0 + v[0]) = 15 candies and box 2 has min(c[2], 0 + v[0]) = 13 candies.

At the end of day 1, box 0 has max(0, 10 + v[1]) = 0 candies, box 1 has max(0, 15 + v[1]) = 4 candies. Since 2 > r[1], there is no change in the number of candies in box 2. The number of candies at the end of each day are summarized below:

As such, the procedure should return [0, 4, 13].

Constraints

• $1 \le n \le 200\,000$
• $1 \le q \le 200\,000$
• $1 \le c[i] \le 10^9$ (for all $0 \le i \le n - 1$)
• $0 \le l[j] \le r[j] \le n - 1$ (for all $0 \le j \le q - 1$)
• $-10^9 \le v[j] \le 10^9, v[j] \neq 0$ (for all $0 \le j \le q - 1$)

Sample Grader

The sample grader reads in the input in the following format:

• line 1: n
• line 2: c[0] c[1] … c[n − 1]
• line 3: q
• line 4 + j (0 ≤ j ≤ q − 1): l[j] r[j] v[j]

The sample grader prints your answers in the following format:

• line 1: s[0] s[1] … s[n − 1]

Execution limits

Your solution will have 4.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "candies.h"

#include <vector>

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    return s;
}

参考函数签名

#include "candies.h"

#include <vector>

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    return s;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "candies.h"

include <vector>

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
std::vector<int> s(n);
return s;
}