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:
#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## 計算量: H*N

N, D, A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]

XH = sorted(XH, key=lambda x: x[0])
X = [XH[i][0] for i in range(N)]
H = [(XH[i][1] + A - 1) // A for i in range(N)] 
## どうせAずつしか体力減らせないので、何回攻撃したら倒せるかに変換

if X[-1] - X[0] <= 2*D:
  ans = max(H)
  print(ans)
  exit()

ans = 0
for i in range(N):
  if H[i] <= 0:
    continue
  else:
    max_index = bisect.bisect_right(X, X[i]+2*D)
    n_attack_i = H[i]
    for j in range(i, max_index):
      H[j] -= n_attack_i
    ans += n_attack_i
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## 計算量: H*N

N, D, A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]

XH = sorted(XH, key=lambda x: x[0])
X = [XH[i][0] for i in range(N)]
H = [(XH[i][1] + A - 1) // A for i in range(N)] 
## どうせAずつしか体力減らせないので、何回攻撃したら倒せるかに変換

if X[-1] - X[0] <= 2*D:
  ans = max(H)
  print(ans)
  exit()

ans = 0
for i in range(N):
  if H[i] <= 0:
    continue
  else:
    max_index = bisect.bisect_right(X, X[i]+2*D)
    n_attack_i = H[i]
    for j in range(i, max_index):
      H[j] -= n_attack_i
    ans += n_attack_i
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = []
    for _ in range(N):
        X, H = map(int, readline().split())
        XH.append((X, (H + A - 1) // A))

    D *= 2
    XH.sort()
    X = [x for x, h in XH]
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        result += h
        bit_add(bit, i, h)

        t = x + D
        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if X[m] <= t:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -h)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = []
    for _ in range(N):
        X, H = map(int, readline().split())
        H = (H + A - 1) // A
        XH.append((X, H))

    XH.sort()
    X = [x for x, h in XH]
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        result += h
        bit_add(bit, i, h)

        t = x + 2 * D
        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if X[m] <= t:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -h)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = []
    for _ in range(N):
        X, H = map(int, readline().split())
        H = (H + A - 1) // A
        XH.append((X, H))

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        result += h
        bit_add(bit, i, h)

        t = x + 2 * D
        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= t:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -h)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [tuple(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        t = x + 2 * D
        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= t:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [tuple(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [list(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    while i <= len(bit):
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [list(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
def bit_add(bit, i, x):
    i += 1
    while i <= len(bit):
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [list(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
import math
#from time import time

#t1 = time()
N, D, A = map(int, input().split())

monsters = [list(map(int, input().split())) for i in range(N)]
monsters.sort(key=lambda i:i[0])

X = [monsters[i][0] for i in range(N)]
H = [monsters[i][1] for i in range(N)]

number = 0
for i in range(N):
	if H[i] > 0:
		num = math.ceil(H[i] / A)
		number += num
		H = [H[j]-num*A if X[j] <= X[i]+2*D else H[j] for j in range(N)]
		#print(H)
	else:
		pass

print(number)
#t2 = time()
#print(t2-t1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D
while True:
    need = counting(XH[begin][1])
    ans += need
    
    # これより手前までを減らす
    end = bisect.bisect_right(X, last)

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D








"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
for i in range(N):
    X.append(XH[i][0])

begin = 0
last = XH[begin][0] + 2*D

# これより手前までを減らす
end = bisect.bisect_right(X, last)

while True:
    need = counting(XH[begin][1])
    ans += need
    

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D
            for j in range(end, N):
                if XH[j][1] > last:
                    end = j
                    break







"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])
    X.append(x1)

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
X.sort()

begin = 0
last = XH[begin][0] + 2*D
while True:
    need = counting(XH[begin][1])
    ans += need
    
    # これより手前までを減らす
    end = bisect.bisect_right(X, last)

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D








"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math

N, D, A = map(int, input().split())
XH = []
for i in range(N):
    x_tmp, h_tmp = map(int, input().split())
    XH.append([x_tmp, h_tmp])

count=0
XH=sorted(XH, key=lambda x:x[0])
while(True):
    min_x=XH[0][0]
    res_h=XH[0][1]
    
    count_plus=math.ceil(res_h/A)
    count+=count_plus
    XH_new=[[x,h] if x > min_x+2*D else [x,h-A*count_plus] for x,h in XH ]
    XH=[[x,h] for x,h in XH_new if h>0]
    
    if len(XH)==0:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
import math

N, D, A = map(int, input().split())
XH = []
for i in range(N):
    x_tmp, h_tmp = map(int, input().split())
    XH.append([x_tmp, h_tmp])

count=0
while(True):
    min_x=min(x for x,h in XH)
    X_only=[x for x,h in XH]
    res_h=XH[X_only.index(min_x)][1]
    
    count_plus=math.ceil(res_h/A)
    count+=count_plus
    XH_new=[[x,h] if x > min_x+2*D else [x,h-A*count_plus] for x,h in XH ]
    XH=[[x,h] for x,h in XH_new if h>0]
    
    if len(XH)==0:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
ans = 0
for x in X:
    if d[x] > 0:
        m = -(-d[x]//A)
        ans += m
        for xx in X:
            if xx <= x + 2*D:
                d[xx] -= m*A
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, D, A = map(int, input().split())
d = defaultdict(int)
X = []
for i in range(N):
    x, h = map(int, input().split())
    d[x] = h
    X.append(x)
X.sort()
ans = 0
for x in X:
    if d[x] > 0:
        m = -(-d[x]//A)
        ans += m
        for xx in X:
            if xx <= x + 2*D:
                d[xx] -= m*A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, intv):
        """
        N:要素数
        func:計算式(maxなど)
        intv:単位元
        """
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        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

    def update(self, l, r, x):
        """ 区間[l,r)の値にxを加算 """

        # 1. lazyの値は伝搬させない
        # 2. 区間[l,r)のdata, lazyの値を更新
        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
        # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
        for i in self.gindex(l, r):
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        """ 区間[l,r)の最小(大)値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小(大)値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

#####

import bisect




N,D,A=map(int,input().split())
XH=[[0,0] for _ in range(N)]

for i in range(N):
    XH[i][0],XH[i][1]=map(int,input().split())
    
XH.sort()

X=[0]*N
for i in range(N):
    X[i]=XH[i][0]


sst=StarrySkyTree(N+1, max, 0)

for i in range(N):
    sst.update(i,i+1,XH[i][1])
    
cnt=0
for i in range(N):
    h=sst.query(i,i+1)
    if h>0:
        r=bisect.bisect_right(X,X[i]+2*D)
        bomb=(h+A-1)//A#切り上げ
        sst.update(i,r,-1*bomb*A)
        cnt+=bomb
        
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	sortedz=1
	for i in range(N):
		#c = [int(i) for i in input().split()]
		a.append([int(i) for i in input().split()])
		if (a[i][0]<a[i-1][0]):
			sortedz=0
	if (sortedz==0):
		a = sorted(a, key=itemgetter(0))
	if (a[-1][0]-a[0][0] <= 2*D):
		max = a[0][1]
		for i in range(1,N):
			if (max<a[i][1]):
				max = a[i][1]
		count = ceil(max/A)
		print (count)
		return
	d=0
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,N):
			if (a[i][1]<=0):
				continue
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	if (a[-1][0]-a[0][0] <= 2*D):
		max = a[0][1]
		for i in range(1,N):
			if (max<a[i][1]):
				max = a[i][1]
		count = ceil(max/A)
		print (count)
		return
	elif (D==0):
		sum =0
		for i in range(N):
			count+=ceil(a[i][1]/A)
		print (count)
		return
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,N):
			if (a[i][1]<=0):
				continue
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	if (a[-1][0]-a[0][0] <= 2*D):
		max = a[0][1]
		for i in range(1,len(a)):
			if (max<a[i][1]):
				max = a[i][1]
		count = ceil(max/A)
		print (count)
		return
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,len(a)):
			if (a[i][1]<=0):
				continue
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,len(a)):
			if (a[i][1]<=0):
				continue
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from math import ceil
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	k=0
	while (1):
		d = ceil(a[k][1]/A)
		count+=d
		kold = k
		a[k][1]=0
		found =0
		for i in range(kold+1,len(a)):
			if(a[i][0]<=(a[kold][0]+2*D)):
				a[i][1]-=(d*A)
				if (found==0 and a[i][1]>0):
					k=i
					found =1
			else:
				if (found==0):
					k=i
					found=1
				break
		if (found==0):
			break
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import math
def main():
	a=[]
	c = [int(i) for i in input().split()]
	N=c[0]
	D=c[1]
	A=c[2]
	count=0
	for i in range(N):
		c = [int(i) for i in input().split()]
		a.append(c)
	a = sorted(a, key=itemgetter(0))
	while (len(a) != 0):
		d = math.ceil(a[0][1]/A)
		count+=d
		deleted=[0]
		for i in range(len(a)):
			if (i==0):
				continue
			if(a[i][0]<=(a[0][0]+2*D)):
				a[i][1]-=(d*A)
				if (a[i][1]<=0):
					deleted.append(i-len(deleted))
			else:
				break
		for i in deleted:
			del a[i]
	print (count)
if __name__== "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N,D,A = map(int, input().split())
    enemy = np.zeros((2,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h
    enemy = enemy[:, np.argsort(enemy[0,:])]

    damagemgr = np.zeros((1,2))
    ans = 0
    for i in range(N):
        x,h = map(int, enemy[:,i])
        #print("enm",x,h)

        pastdm = np.zeros((1,2))
        futureidx = 0
        flag = False
        for i in range(damagemgr.shape[0]):
            dm = damagemgr[i,:]
            #print("dm",dm)
            if x > int(dm[1]) :
                h += int(dm[0])
                pastdm[0,0] += dm[0]
                pastdm[0,1] = dm[1]
                flag = True
            else:
                if flag:
                    futureidx = i
                    flag = False
        if not futureidx==0: damagemgr = np.vstack((pastdm,damagemgr[futureidx:,:]))


        #print(h)
        if h > 0:
            atack = int( (h + A - 1)/A )
            ans += atack
            damage = atack * A
            #print("atk",h,atack,damage)
            damagemgr = np.vstack( (damagemgr, [damage,x+2*D] ) )
            enemy[1,:] -= damage
        #print("")

    """
    while sum( (enemy[1,:]>0) )  :
        #print(enemy)
        atack = int( (enemy[1,0] + A - 1)/A )
        ans += atack
        damage = atack * A
        #print("damage",damage)
        for d_range in range(enemy.shape[1]):
            if enemy[0,d_range] > enemy[0,0] + 2*D : break
        if d_range == enemy.shape[1]-1 and enemy[0,-1] <= enemy[0,0] + 2*D : d_range += 1
        #print("d_range",d_range)
        enemy[1,:d_range] -= damage

        for survive in range(enemy.shape[1]):
            if enemy[1,survive] > 0: break
        enemy = enemy[:,survive:]
        #print("survive",survive,ans)
    """

    print(ans)
    return


"""
def old0208():
    N,D,A = map(int, input().split())
    enemy = np.zeros((3,N))
    for i in range(N):
        x,h = map(int, input().split())
        enemy[:,i] = x,h, int(h/A) + (h%A>0)

    farest = int(enemy[0].max()+1)
    enemylist = [0]*farest
    for i in range(N):
        enemylist[ int(enemy[0,i]) ] = enemy[2,i]
    
    ans = 0
    while sum(enemylist)>0:
        pos = [0]*farest
        for i in range(farest):
            pos[i] = sum(enemylist[i-D:i+D+1])
        bestpos = pos.index(max(pos))
        for i in range(bestpos-D,bestpos+D+1):
            if enemylist[i]>0: enemylist[i] = enemylist[i]-1
        ans += 1

    print(ans)
    return
"""

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]###(*)
  ###これまでのやつに与えたダメージは引き継がれるものとする
  d = ds[i]
  if d>=h:
    continue###すでに体力以上のダメージを与えた敵
  h -= d###ダメージを与える
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  ###(*)のせいで, 2Dよりも向こう側にも、今考えたダメージの影響が
  ###出てしまうので. それを打ち消すために与えるダメージを引いておく
  b += times
print(b)