Problem:


Score : 600 points

Problem Statement

Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A.
There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

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

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline


class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    # 遅延伝搬処理
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline


class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1
    
    # 遅延伝搬処理
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    tree = LazySegTree(N)
    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i in range(N):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, m[i]+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
input=sys.stdin.readline
N, D, A = map(int, input().split())

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


def set_list(l, N):
    for i in range(N):
        data[i+N0-1] = l[i]
    for i in range(N0-1)[::-1]:
        data[i] = max(data[2*i+1], data[2*i+2])


def solve():
    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    set_list(l, N)

    ans = 0
    for i in range(N):
        v = query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, m[i]+2*D)
            update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N, D, A = map(int, input().split())

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


def set_list(l, N):
    for i in range(N):
        data[i+N0-1] = l[i]
    for i in range(N0-1)[::-1]:
        data[i] = max(data[2*i+1], data[2*i+2])


def solve():
    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    set_list(l, N)

    ans = 0
    for i in range(N):
        v = query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, m[i]+2*D)
            update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N, D, A = map(int, input().split())

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


def solve():
    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    for i, h in enumerate(l):
        update(i, i+1, h)

    ans = 0
    for i in range(N):
        v = query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, m[i]+2*D)
            update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N, D, A = map(int, input().split())

l = [tuple(map(int, input().split())) for _ in range(N)]
l.sort()

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


m = []
for i, (x, h) in enumerate(l):
    update(i, i+1, h)
    m.append(x)

ans = 0
for i in range(N):
    v = query(i, i+1)
    if v>0:
        c = (v+A-1)//A
        ans += c
        pos = bisect_right(m, m[i]+2*D)
        update(i, pos, -c*A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math


def solve(N: int, D: int, A: int, X: "List[int]", H: "List[int]"):
    M = sorted([(X[i], H[i]) for i in range(N)])
    DD = 2*D
    result = 0
    next = 0
    while next <= N-1:
        hasNonZero = False
        breaken = False
        left = M[next]
        attackCount = math.ceil(left[1]/A)
        damage = attackCount*A
        result += attackCount
        # print(f"max X:{left[0]+DD}")
        for i in range(next, N):
            if M[i][0] <= left[0]+DD:
                M[i] = (M[i][0], max(0, M[i][1]-damage))
                if not hasNonZero and M[i][1] != 0:
                    hasNonZero = True
                    breaken = True
                    next = i
            else:
                if not hasNonZero:
                    next = i
                breaken = True
                break
        if not breaken:
            next = N
        # print(f"next:{next}")
        # print(M)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    H = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        H[i] = int(next(tokens))
    solve(N, D, A, X, H)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
n,d,a = map(int,input().split())
L = []
kyo = []
s = 0
for i in range(n):
    x,h = map(int,input().split())
    L.append([x,h])
    kyo.append(x)
    s += h
L.sort()
kyo.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        times = int(math.ceil(L[temp][1]/a))
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        k = bisect.bisect_right(kyo, ran)
        next = temp+1
        for i in range(temp+1, k):
            if L[i][1] > damage:
                L[i][1] -= damage
                s -= damage
                next = min(next, i)
            else:
                s -= L[i][1]
                L[i][1] = 0
        temp = next
    else:
        for i in range(temp+1, n):
            if L[i] != 0:
                temp = i
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d,a = map(int,input().split())
L = []
s = 0
for i in range(n):
    t = list(map(int,input().split()))
    s += t[1]
    L.append(t)
L.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        times = int(math.ceil(L[temp][1]/a))
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        next = temp+1
        for i in range(temp+1, n):
            if L[i][0] <= ran:
                if L[i][1] > damage:
                    L[i][1] -= damage
                    s -= damage
                    next = min(next, i)
                else:
                    s -= L[i][1]
                    L[i][1] = 0
            else:
                break
        temp = next
    else:
        for i in range(temp+1, n):
            if L[i] != 0:
                temp = i
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int,input().split())
L = []
s = 0
for i in range(n):
    t = list(map(int,input().split()))
    s += t[1]
    L.append(t)
L.sort()
ans = 0
temp = 0
while s != 0:
    if L[temp][1] != 0:
        if L[temp][1]%a == 0:
            times = L[temp][1]//a
        else:
            times = L[temp][1]//a+1
        ans += times
        s -= L[temp][1]
        damage = a*times
        ran = L[temp][0]+2*d
        next = temp+1
        for i in range(temp+1, n):
            if L[i][0] <= ran:
                if L[i][1] > damage:
                    L[i][1] -= damage
                    s -= damage
                    next = min(next, i)
                else:
                    s -= L[i][1]
                    L[i][1] = 0
            else:
                break
        temp = next
    else:
        temp += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,d,a = map(int, input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()

from collections import deque
dmg_lis=deque()
ans=0
for tmp in xh:
    x=tmp[0]
    h=tmp[1]

    rm_cnt=0
    for x_dmg in dmg_lis:
        if x<=x_dmg[0]:
            h-=x_dmg[1]
        else:
            rm_cnt+=1
    for i in range(rm_cnt):
        dmg_lis.popleft()
    if h<=0:
        continue

    max_x=x+2*d
    num=((h - 1) // a) + 1
    dmg = num*a
    ans+=num

    dmg_lis.append([max_x,dmg])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,d,a = map(int, input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()

dmg_lis=[]
ans=0
for tmp in xh:
    x=tmp[0]
    h=tmp[1]

    for x_dmg in dmg_lis:
        if x<=x_dmg[0]:
            h-=x_dmg[1]
    if h<=0:
        continue

    max_x=x+2*d
    num=((h - 1) // a) + 1
    dmg = num*a
    ans+=num

    dmg_lis.append([max_x,dmg])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
cnt = 0
for i in range(n):
    if h[i] <= 0:
        continue
        
    idx = bisect_right(x, x[i] + 2 * d)
    cur_cnt = -(-h[i] // a)
    for j in range(i, idx):
        h[j] -= cur_cnt * a
    
    cnt += cur_cnt
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

n,d,a = map(int,input().split())
li = []
z = []
for _ in range(n):
    aa,bb = [int(x) for x in input().split()]
    li.append([aa,bb])
    z.append(aa)
li.sort()
z.sort()

ans = 0
for i in range(n):
    x = li[i]
    if x[1]<=0:
        continue
    p = x[0] + d
    index = bisect.bisect_right(z,p+d)
    num = math.ceil(x[1]/a)
    ans += num
    for j in range(i,index):
        li[j][1] -= a * num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

n,d,a = map(int,input().split())
li = []
for _ in range(n):
    li.append([int(x) for x in input().split()])
li.sort()
z = []
h = []
for i in li:
    z.append(i[0])
    h.append(i[1])

ans = 0
for i in range(n):
    if h[i]<=0:
        continue
    p = z[i] + d
    index = bisect.bisect_right(z,p+d)
    num = math.ceil(h[i]/a)
    ans += num
    for j in range(i,index):
        h[j] -= a * num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_right
from math import ceil

N, D, A = map(int, input().split())
monsters = [(-1, -1)]
for _ in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()
#print("monsters = {}".format(monsters))
"""
どうせ左端のモンスターはいつか倒さないといけない（かつ爆弾投下順は不問）ので、
左端のモンスターから順に、なるべく爆弾を右に寄せて落としていけば良い。

別解としてBITでも殴ってみた
"""
class BIT:
    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    """
    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)

"""
BITで区間に対する加算をする場合はimos法を利用することに注意する
"""

Damage = BIT(N)
ans = 0
for i in range(1, N + 1):
    x, h = monsters[i]
    d = Damage.sum(i) # モンスターiに入っているダメージ
    if d < h:
        times = ceil((h - d) / A)
        ans += times
        new_damage = times * A
        #print("ans+={} for monster {}".format(times, i))

        idx = bisect_right(monsters, (monsters[i][0] + 2 * D, 10**10))
        Damage.add(i, new_damage)
        if idx != N + 1:
            Damage.add(idx, -new_damage)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v, is_ok):
    """
    ソートしてから使え！！！
    v : list
        ある場所から左が条件を満たさず、右が条件を満たすように並んだ配列
    is_ok(x) : bool
        vの要素xが条件を満たすかどうかを返す関数
    """
    ng = -1             # 条件を満たさないiのうち今わかっている中で最大の値(v[0]が条件を満たすかもしれないので-1から)
    ok = len(v)         # 条件を満たすiのうち今わかっている中で最小の値(v[n-1]が条件を満たさないかもしれないのでnから)
    # okをできるだけ左に移動させてreturnする

    # ...... ng ok ......
    #          | ->
    # こうなるまで
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2

        if is_ok(v[mid]):   # v[mid]はokであることがわかった
            ok = mid        # okを左に移動
        else:               # v[mid]はngであることがわかった
            ng = mid        # ngを右に移動

    return ok



N, D, A = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(N)]
XH.sort()
X = [x for x, h in XH]
H = [(h + A - 1) // A for x, h in XH]

yuukou = 0
mou_mukou = [0] * N + [0]
ans = 0

# lを左端としてn個爆弾を使う
def bomb(l, n):
    global ans, yuukou
    ans += n
    yuukou += n
    r = l + 2 * D
    mou_mukou[binary_search(X, lambda x: r < x)] += n

for i in range(N):
    yuukou -= mou_mukou[i]
    H[i] -= yuukou
    if H[i] > 0:
        bomb(X[i], H[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


def compress(array):
    """座標圧縮したリストを返す"""
    array2 = sorted(set(array))
    memo = {value: index for index, value in enumerate(array2)}
    return memo

n, d, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

info = sorted(info)
b = [info[i][0] for i in range(n)]
memo = compress([info[i][0] for i in range(n)])
bit = BIT(n)

for i in range(n):
    ind, val = info[i]
    bit.add(memo[ind], memo[ind] + 1, val)

ans = 0
for i in range(n):
    tmp = bit.get_val(i)
    if tmp <= 0:
        continue
    ans += -((-tmp) // a)
    ind, _ = info[i]
    nxt_ind = ind + 2 * d
    ii = bisect.bisect_right(b, nxt_ind)
    bit.add(i, ii, ((-tmp) // a) * a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, D, A = MI()
monsters = list()
for i in range(N):
    x, h = MI()
    monsters.append((x, (h + A - 1) // A))
monsters.sort()

ans = 0
for i, (x, h) in enumerate(monsters):
    if h > 0:
        ans += h
        j = i + 1
        while j < N:
            xj, hj = monsters[j]
            if xj > x + 2 * D:
                break
            monsters[j] = (xj, max(0, hj - h))
            j += 1
print(ans)