Будем заполнять исходный массив последовательно, поддерживая последнее известное значение суммы. Если p_i =  - 1, то положим a_i = m, потому что меньшее значение записать нельзя, а большее возможно помешает в дальнейшем.

При этом, если p_i ≠  - 1, то положим a_i = p_i - pref_sum, где pref_sum — сумма уже заполненных элементов a. Если в таком случае, a_i оказалось меньше m, то решения не существует, так как pref_sum минимально возможный по построению.

Итоговая сложность представленного решения O(n).