Problem:


					Max Score: $1200$ Points 

Problem statement

						There are $N$ customers in a restaurant. Each customer is numbered $1$ through $N$. 

						A sushi chef carried out $Q$ operations for customers. 

						The $i$-th operation is follows: 

The sushi chef chooses a customer whose number of dishes of sushi eaten is minimum, in customer $1, 2, 3, \dots, a_i$. If there are multiple customers who are minimum numbers of dishes, he selects the minimum-numbered customers. 

He puts a dish of sushi on the selected seats.

A customer who have selected for professional eats this sushi.

Repeat 1-3, $b_i$ times.

						Please calculate the number of dishes of sushi that have been eaten by each customer.

Input

							The input is given from Standard Input in the following format: 

$N \ Q$
$a_1 \ b_1$
$a_2 \ b_2$
$ ：  \ ： $
$a_Q \ b_Q$

Output

You have to print $N$ lines.

The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

$3 \le N, Q \le 100,000$

$1 \le a_i \le N$

$1 \le b_i \le 10^{12}$

Any final results do not exceed $2 \times 10^{13}$.

Subtasks

							Subtask 1 [ $60$ points ] 

$N, Q \le 100$

$b_i = 1$

							Subtask 2 [ $400$ points ] 

$N, Q \le 100$

$b_i \le 10^{12}$

							Subtask 3 [ $240$ points ] 

$N, Q \le 100,000$

$b_i = 1$

							Subtask 4 [ $500$ points ] 

There are no additional constraints.

Sample Input 1

9 3
5 11
8 4
4 7

Sample Output 1

4
4
4
4
2
2
1
1
0

						The change of the number of dishes of sushi have eaten is following: 

Customer 1
Customer 2
Customer 3
Customer 4
Customer 5
Customer 6
Customer 7
Customer 8
Customer 9

1st Operation
3 2 2 2 2 0 0 0 0

2nd Operation
3 2 2 2 2 2 1 1 0

3rd Operation
4 4 4 4 2 2 1 1 0

Sample Input 2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

Sample Output 2

10
10
5
5
4
2

Sample Input 3

5 6
1 1
2 1
3 1
1 1
5 1
3 1

Sample Output 3

2
2
1
1
0

Sample Input 4

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100

Sample Output 4

223
123
77
50
33
21
12
7
3
1

				Writer: E869120 



Sample input:
9 3
5 11
8 4
4 7


Sample output:
4
4
4
4
2
2
1
1
0

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8, i8[:]), cache=True)
def main(N, AB):
    A, B = AB[::2], AB[1::2]
    Q = len(A)

    bit = np.zeros(N + 1, np.int64)  # 長方形の右上になる x 座標集合を管理
    bit_raw = np.zeros(N + 1, np.int64)
    H = np.zeros(N + 1, np.int64)  # 長方形の高さを管理
    H[0] = 10**13 + 10
    bit_raw[N] = 1
    add(bit, N, 1)

    for i in range(Q):
        a, b = A[i], B[i]
        n = get_sum(bit, a - 1)
        h = H[find_kth_element(bit, 1 + n)]
        if not bit_raw[a]:
            bit_raw[a] = 1
            add(bit, a, 1)
            H[a] = h
        r = a

        while b:
            l = 0 if n == 0 else find_kth_element(bit, n)
            n -= 1
            area = (H[l] - H[r]) * (r - l)
            if area <= b:
                b -= area
                if l:
                    bit_raw[l] = 0
                    add(bit, l, -1)
                H[l], H[r] = 0, H[l]
                continue
            k = b // (r - l)
            b -= k * (r - l)
            H[r] += k
            if b:
                m = l + b
                bit_raw[m] = 1
                add(bit, m, 1)
                H[m] = H[r] + 1
                b = 0
    for n in range(N, 0, -1):
        H[n - 1] = max(H[n - 1], H[n])
    return H[1:N + 1]

N, Q = map(int, readline().split())
AB = np.array(read().split(), np.int64)

ans = main(N, AB)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8, i8[:]), cache=True)
def main(N, AB):
    A, B = AB[::2], AB[1::2]
    Q = len(A)

    bit = np.zeros(N + 1, np.int64)  # 長方形の右上になる x 座標集合を管理
    bit_raw = np.zeros(N + 1, np.int64)
    H = np.zeros(N + 1, np.int64)  # 長方形の高さを管理
    H[0] = 2 * 10**13 + 10
    bit_raw[N] = 1
    add(bit, N, 1)

    for i in range(Q):
        a, b = A[i], B[i]
        n = get_sum(bit, a - 1)
        h = H[find_kth_element(bit, 1 + n)]
        if not bit_raw[a]:
            bit_raw[a] = 1
            add(bit, a, 1)
            H[a] = h
        r = a

        while b:
            l = 0 if n == 0 else find_kth_element(bit, n)
            n -= 1
            area = (H[l] - H[r]) * (r - l)
            if area <= b:
                b -= area
                if l:
                    bit_raw[l] = 0
                    add(bit, l, -1)
                H[l], H[r] = 0, H[l]
                continue
            k = b // (r - l)
            b -= k * (r - l)
            H[r] += k
            if b:
                m = l + b
                bit_raw[m] = 1
                add(bit, m, 1)
                H[m] = H[r] + 1
                b = 0
    for n in range(N, 0, -1):
        H[n - 1] = max(H[n - 1], H[n])
    return H[1:N + 1]

N, Q = map(int, readline().split())
AB = np.array(read().split(), np.int64)

ans = main(N, AB)
print('\n'.join(map(str, ans.tolist())))