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:
N,D,A = map(int, input().split())
P=[]
for i in range(N):
    L = list(map(int, input().split()))
    if(L[1]%A==0):
        L[1]=int(L[1]/A)
    else:
        L[1]=int(L[1]/A)+1
    L.append(L[0]-D)
    L.append(L[0]+D)
    P.append(L)
P.sort()
#print(P)
ans=0
for i in range(N):
    if(P[i][1]>0):
        ans=ans+P[i][1]
        #P[i][1]=0
        for j in range(i+1,N):
            if(P[i][3]>=P[j][2]):
                P[j][1]=P[j][1]-P[i][1]
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import operator

inp = raw_input().split()
N = int(inp[0])
D = int(inp[1])
A = int(inp[2])
inp = [raw_input().split() for i in range(N)]
XH = []
for i in inp:
	XH.append([int(i[0]), int(i[1])])

def bomb():
	XH.sort(key=operator.itemgetter(0))
	sum_number = 0
	while len(XH) != 0:
		number = XH[len(XH)-1][1] // A
		if XH[len(XH)-1][1] % A != 0:
			number += 1
		for i in XH:
			if i[0] >= XH[len(XH)-1][0] - 2*D:
				i[1] = i[1] - A * number
				if i[1] < 0:
					i[1] = 0
		sum_number += number
		while not (XH == []) and XH[len(XH)-1][1] == 0:
			XH.pop()
	return sum_number

ans = bomb()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N, D, A = map(int, input().split())
lst = []
for i in range(N):
	X, H = map(int, input().split())
	lst.append([X, math.ceil(H / A)])
lst.sort(key = lambda x : x[0])

ans = 0

while lst:
	x, y = lst.pop(0)
	if y <= 0: continue
	place = -100
	for i in range(len(lst)):
		if x + 2 * D < lst[i][0]:
			place = i
			break
		else:
			lst[i][1] -= y
	ans += y
		
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input = sys.stdin.readline
N, D, A = map(int,input().split())
XH = []
for i in range(N):
    XH.append(list(map(int,input().split())))
XH.sort()
ans = 0
for i in range(N):
    if XH[i][1] > 0:
        p = XH[i][0]
        t = A*math.ceil(XH[i][1] / A)
        ans += math.ceil(XH[i][1] / A)
        for l in range(i, N):
            if XH[l][0] <= p + 2 * D:
                XH[l][1] -= t
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = list(map(int,input().split()))
X=[]
H=[]
for i in range(N):
    x,h = list(map(int,input().split()))
    X.append(x)
    H.append(h)
# print("X",X,"H",H)

def n_att(h,a):
    return int(abs(-h//a))

count = 0

while H:
    #モンスターがいる最小の座標を見つける。
    xmin = min(X)
    # print(xmin)
    
    #爆弾を投げる回数を決定
    h = H[X.index(xmin)]
    n = n_att(h,A)
    damage = n*A
    count += n
    #xmin+Dに爆弾を投げる。
    for i in range(len(X)):
        if xmin<=X[i]<=xmin+2*D:
            if H[i]>damage:
                H[i] -= damage
            else:
                H[i] = 0
    # print(H)
    
    #0以下のリストを消す。
    i = 0
    while 1==1:
        try:
            if H[i] <= 0:
                X.pop(i)
                H.pop(i)
            else:
                i += 1
        except:
            break
    # print(H)
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import numpy as np

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

M = M[np.argsort(M[:, 0])]
X = M[:, 0]
H = M[:, 1]
ans = 0
for i in range(N):
    if H[i] <= 0:
        continue
    blast_r = X[i] + 2 * D
    max_j = bisect_right(X, blast_r, i + 1)
    c = (H[i] + A - 1) // A
    ans += c
    if i + 1 < max_j:
        H[i + 1:max_j] -= A * c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())

enemy = []

for i in range(n):
    enemy.append(list(map(int, input().split())))

enemy = sorted(enemy)

ans = 0

attack_log = []

for i in range(len(enemy)):
    x, hp = enemy[i]
    pop_count = 0
    for p, damage in attack_log:
        if x <= p:
            hp -= damage
            if hp < 0:
                break
        else:
            pop_count += 1

    for j in range(pop_count):
        attack_log.pop(0)

    
    if hp > 0:
        attack = -(-hp//a)
        ans += attack

        pos = x + d * 2
        dam = a * attack
        attack_log.append([pos, dam])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D,A = map(int, input().split())
P = sorted([ list(map(int,input().split(" "))) for i in range(N)])
cnt = 0
k = 0
for i in range(N):
    if P[i][1]>0:
        k = -(-P[i][1]//A)
        cnt += k 
        for j in range(1,N-i):
            if P[i+j][0]<=P[i][0]+2 * D:
                P[i+j][1] += -k*A
            else:
                break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math


def main():
        
    N,D,A = map(int, input().split())

    xh = [list(map(int, input().split())) for _ in range(N)]

    xh.sort()

    ans = 0
    for i in range(N):
        if xh[i][1] <= 0:
            continue


        
        cnt = math.ceil(xh[i][1] / A)
        ans += cnt
        xh[i][1] = 0

        if cnt == 0:
            continue

        d = cnt*A
        for j in range(i+1, N):

            if xh[j][0] > xh[i][0] + 2*D:
                break
            xh[j][1] -= d


    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())

enemy = []

for i in range(n):
    enemy.append(list(map(int, input().split())))

enemy = sorted(enemy)

ans = 0

attack_log = []

for i in range(len(enemy)):
    x, hp = enemy[i]
    pop_count = 0
    for p, damage in attack_log:
        if x <= p:
            hp -= damage
        else:
            pop_count += 1

    # for j in range(pop_count):
        # attack_log.pop(0)

    
    if hp > 0:
        attack = -(-hp//a)
        ans += attack

        pos = x + d * 2
        dam = a * attack
        attack_log.append([pos, dam])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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()
ans = 0
for i, name in enumerate(XH):
    if name[1] > 0:
        p = name[0]
        t = A*math.ceil(name[1] / A)
        ans += math.ceil(name[1] / A)
        for l in XH[i::]:
            if l[0] <= p + 2 * D:
                l[1] -= t
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]
  XH.sort(key=lambda x:x[0])
  #print(XH)

  B = []
  ans = 0
  for x,h in XH:
    BB = []
    for s,t,c in B:
      #print(s,t,c,x)
      if s <= x <= t:
        h -= A*c
        BB.append((s,t,c))
    #print(h)
    if h > 0:
      BB.append((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
    #print(ans,x,x+2*D,(h+A-1)//A,B)
    B = BB[:]
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import bisect
N,D,A = map(int,input().split())
X = np.zeros(N,dtype=int)
H = np.zeros(N,dtype=int)
for i in range(N):
    X[i],H[i] = map(int,input().split())
idx = np.argsort(X)
X = X[idx]
H = H[idx]

now = 0
count = 0

while(1):
    while(H[now] <= 0):
        now += 1
        if(now >= N):
            print(count)
            exit()
    
    tx = X[now] + D
    num = H[now] // A
    if(H[now] % A != 0):num += 1
    idxl = bisect.bisect_left(X,tx-D)
    idxr = bisect.bisect_right(X,tx+D)
    H[idxl:idxr] -= num * A
    count += num

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
lst.append([10**11, 0])

# x, h = [], []
# for i in range(n):
#     x.append(lst[i][0])
#     h.append(lst[i][1])

# x.append(10**11)
# h.append(0)

kougeki_start = 0
kougeki_end = 0
cnt = 0
for i in range(n):
    if lst[i][1] > 0:
        left = i # 可能
        right = n # 不可能
        while left+1 < right:
            mid = (left + right) // 2
            if lst[mid][0] - lst[i][0] <= 2*d:
                left = mid
            else:
                right = mid
        cnt += lst[i][1]
        hiku = lst[i][1]
        for j in range(i, left+1):
            lst[j][1] -= hiku

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,D,A = map(int,readline().split())
mons = [list(map(int,readline().split())) for i in range(N)]
for i in range(N):
    mons[i][1] = (mons[i][1]+A-1)//A

mons.sort(key=lambda x: x[0])

ans = 0
for i in range(N):
    if mons[i][1] > 0:
        c = mons[i][1]
        mons[i][1] = 0
        ans += c
        for j in range(i+1,N):
            if mons[j][0] <= mons[i][0]+2*D:
                mons[j][1] -= c
            else:
                break

#print(mons)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
cnt = 0
cur = 0
while cur<N:
    x = X[cur][0]
    if X[cur][1]%A==0:
        n = X[cur][1]//A
    else:
        n = X[cur][1]//A+1
    ind = bisect_right(X,[x+2*D,10**10])
    for i in range(cur,ind):
        X[i][1] -= n*A
    cnt += n
    flag = 0
    for i in range(cur+1,N):
        if X[i][1]>0:
            cur = i
            flag = 1
            break
    if flag==0:cur=N
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())

enemy = []

for i in range(n):
    enemy.append(list(map(int, input().split())))

enemy = sorted(enemy)

ans = 0

attack_log = []

for i in range(len(enemy)):
    x, hp = enemy[i]
    pop_count = 0
    for p, damage in attack_log:
        if x <= p:
            hp -= damage
        else:
            pop_count += 1

    for j in range(pop_count):
        attack_log.pop(0)

    
    if hp > 0:
        attack = -(-hp//a)
        ans += attack

        pos = x + d * 2
        dam = a * attack
        attack_log.append([pos, dam])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,d,a = map(int,input().split())
mons=[]
for i in range(n):
    x,h=map(int,input().split())
    mons.append([x,h])
mons.sort()
damages = np.zeros(n)
right_idx=0

cnt = 0
for i in range(n):
    x,h = mons[i]
    h -= damages[i]
    if h<0:
        continue
    left_x = x
    left_idx = i
    right_x = x + 2*d
    tmp=0
    while(1):
        if right_idx+tmp == n or mons[right_idx+tmp][0]>right_x:
            right_idx += tmp
            break
        tmp+=1
    c = int(h//a + int(bool(h%a)))
    damage = a*c
    cnt += c
    damages[left_idx:right_idx] += damage
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,D,A = LI()

def check(x,M):
    M_ = [[a,b] for a,b in M]
    count = 0
    for i in range(N):
        if M_[i][1] > 0:
            bomb = (M_[i][1]+A-1)//A
            count += bomb
            if count > x:
                return False

            damage = bomb * A
            for j in range(i,N):
                if M_[j][0] <= M_[i][0] + 2*D:
                    M_[j][1] = max(0,M_[j][1] - damage)
                else:
                    break
    return True

def main():
    M = []
    for i in range(N):
        M.append(LI())
    M.sort(key = lambda x: x[0])

    isNG = 0
    isOK = N*((10**9)+A-1)//A

    while(isNG+1 != isOK):
        mid = (isNG+isOK)//2
        if check(mid,M):
            isOK = mid
        else:
            isNG = mid
    print(isOK)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 1
    bit = defaultdict(int)
    for i in range(n):
        x, h = xh[i]
        h -= bit[i]
        if h > 0:
            t = (h - 1) // a + 1
            for ldi in range(i, n):
                if x + 2 * d >= xh[ldi][0]:
                    bit[ldi] += t * a
                    continue
                break
            ans += t
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math
nda=input().split(" ")
N=int(nda[0])
D=int(nda[1])
A=int(nda[2])
XH=[]
for i in range(N):
    s=input().split(" ")
    XH+=[[int(s[0]),int(s[1])]]
XH.sort()
#print(XH)

ans=0
LXH=len(XH)
while LXH>0:
    bombpoint=XH[0][0]+D
    bombcount=math.ceil(XH[0][1]/A)
    ans+=bombcount
    i=0
    while True:
        if i>=LXH:
            break
        if XH[i][0]<=bombpoint+D:
            XH[i][1]-=bombcount*A
            if XH[i][1]<=0:
                XH.pop(i)
                LXH-=1
            else:
                i+=1
        else:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0], reverse=True)

ans = 0
for i,xh in enumerate(XH):
    X = xh[0]
    H = xh[1]
    if H > 0:
        num = ceil(H/A)
        for j in range(i,N):
            if XH[j][0] >= X-2*D:
                XH[j][1] -= A*num
            else:
                break
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_dict = dict()
hp_dict = dict()
for j in range(N):
    monster_place, monster_hp = map(int, input().split())
    place_dict[monster_place] = j
    hp_dict[j] = monster_hp
ans = 0

place_dict = sorted(place_dict.items(), key=lambda x: x[0])

# print(place_dict)
for i in range(N):
    place = place_dict[i][0]
    index = place_dict[i][1]
    if index not in hp_dict:
        continue
    else:
        bomb = math.ceil(hp_dict[index] / A)
        # print(bomb)
        ans += bomb
        for k in range(i, N):
            if place_dict[k][0] > place + 2 * D:
                break
            elif place_dict[k][1] not in hp_dict:
                continue
            else:
                hp_dict[place_dict[k][1]] -= bomb * A
                if hp_dict[place_dict[k][1]] <= 0:
                    del hp_dict[place_dict[k][1]]
print(ans)
# print(hp_dict)

Submission status: Time Limit Exceeded

Solution code:
n,d,a = map(int, input().split())
xh = []
ans = 0
for i in range(n):
    x,h = map(int, input().split())
    xh.append([x,h])

xh.sort()



while n != 0:
    z = (xh[0][1] - 1) // a + 1
    ans += z
    m = z * a
    r = xh[0][0] + 2 * d
    l = []
    for i in range(n):
        if xh[i][0] > r:
            break
        if xh[i][1] <= m:
            l = [i] + l
            n -= 1
        else:
            xh[i][1] -= m
    for i in range(len(l)):
        del xh[l[i]]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
N, D, A = map(int, input().split())

ys = []
for _ in range(N):
    X, H = map(int, input().split())
    ys.append((X, 0, -(-H//A)))
    ys.append((X+2*D, 1, -(-H//A)))

ys = sorted(ys, key=lambda x : (x[0],x[1]))
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, f, h) in enumerate(ys):
    if f:
        d1[y-2*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)

Submission status: Time Limit Exceeded

Solution code:

N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, D, A = map(int, input().split())
    XH = []
    for i in range(N):
        x, h = map(int, input().split())
        h = (h + (A - 1)) // A
        XH.append([x, h])

    XH.sort()
    result = 0
    for i in range(N):
        x, h = XH[i]
        if h < 0:
            continue
        result += h
        for j in range(i + 1, N):
            if XH[j][0] > x + 2 * D:
                break
            XH[j][1] -= h
    print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

N,D,A=map(int,input().split())
List=[list(map(int,input().split())) for i in range(N)]
List.sort()
arr = []
Harr = [0] * (N+1)

for i in range(N):
  X = List[i][0]
  H = List[i][1]
  H = math.ceil(H / A)
  arr .append(X)
  Harr[i] = H
  
cnt = 0
for i in range(len(arr)):
  r = int(arr[i])
  while Harr[i] > 0:
    a = bisect.bisect_right(arr, r+2*D)
    T = int(Harr[i])
    for j in range((a-i)):
      Harr[i+j] -= int(T)
    cnt += int(T)
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

n, d, a = map(int, input().split()) 
monsters = sorted([list(map(int, input().split())) for _ in range(n)])
x = [m[0] for m in monsters ]

ans = 0
for i, (xi, hi) in enumerate(monsters):
  if (hi > 0):
    times = math.ceil(hi / a) 
    dmg= times * a
    ans += times
    index_r = bisect.bisect_right(x, xi + 2 * d, lo=i, hi=n)
    if (i < n - 1):
      for monster in monsters[i + 1: index_r]:
        monster[1] = max(0, monster[1] - dmg)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
mons = [list(map(int,input().split())) for i in range(N)]
for i in range(N):
    mons[i][1] = (mons[i][1]+A-1)//A

mons.sort(key=lambda x: x[0])

ans = 0
for i in range(N):
    if mons[i][1] > 0:
        c = mons[i][1]
        mons[i][1] = 0
        ans += c
        for j in range(i+1,N):
            if mons[j][0] <= mons[i][0]+2*D:
                mons[j][1] -= c
            else:
                break

#print(mons)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
    N, D, A = list(map(int,input().split()))
    XH = [list(map(int,input().split())) for i in range(N)]
    
    XH = sorted(XH, key = lambda x:int(x[0]))
    
    target_mon = 0
    total_bom = 0
    for k in range(1000000):
        target_bom = XH[target_mon][0] + D
        bom_range = target_bom + D
        bom_num = math.ceil(XH[target_mon][1]/A)
        total_bom += bom_num
        
        for j in range(N):
            if XH[j][0] <= bom_range:
                XH[j][1] -= bom_num*A
                
        for j in range(N):
            if XH[j][1] > 0:
                target_mon = j
                break
        else:
            break
           
    print(total_bom)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A = list(map(int,input().split()))
X=[]
H=[]
for i in range(N):
    x,h = list(map(int,input().split()))
    X.append(x)
    H.append(h)
# print("X",X,"H",H)

def n_att(h,a):
    return int(abs(-h//a))

count = 0

while H:
    #モンスターがいる最小の座標を見つける。
    xmin = min(X)
    # print(xmin)
    
    #爆弾を投げる回数を決定
    h = H[X.index(xmin)]
    n = n_att(h,A)
    count += n
    #xmin+Dに爆弾を投げる。
    for i in range(len(X)):
        if xmin<=X[i]<=xmin+2*D:
            H[i] -= n*A
    # print(H)
    
    #0以下のリストを消す。
    i = 0
    while 1==1:
        try:
            if H[i] <= 0:
                X.pop(i)
                H.pop(i)
            else:
                i += 1
        except:
            break
    # print(H)
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
if m[0][1] < m[-1][1]:
    for i in range(n):
        m[i][0] = m[i][0] * (-1)
    m.reverse()
bomb = [0 for _ in range(n)]
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    bomb[i] = r - 1
res = 0
for i in range(n):
    if m[i][1] > 0:
        tres = (m[i][1] + a - 1) // a
        res += tres
        dh = tres * a
        for j in range(i, bomb[i] + 1):
            m[j][1] -= dh
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
import bisect

n, d, a = [int(item) for item in input().split()]
places = []
xh = []
for i in range(n):
    x, h = [int(item) for item in input().split()]
    xh.append((x, h))
    places.append(x)
xh.sort()
places.sort()

N = 2**((n - 1).bit_length())
data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0
for i, (x, h) in enumerate(xh):
    init_damage = (query(1, i+2) - query(1, i+1)) * a
    if init_damage >= h:
        continue
    bomb = (h - init_damage + a - 1) // a
    ans += bomb
    r_lim = bisect.bisect_right(places, x+2*d)
    add(1, r_lim+1, bomb)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right


class SegTree:

    def __init__(self, a_list, x_list):
        assert max(a_list) <= 10 ** 7
        assert min(a_list) >= 0
        self.n = 1
        m = max(a_list)
        while self.n <= m:
            self.n *= 2
        self.dat_a = [0] * (self.n * 2)
        self.dat_b = [0] * (self.n * 2)
        for a, x in zip(a_list, x_list):
            self._add(a, a + 1, x, 0, 0, self.n)

    def _add(self, a, b, x, k, left, right):
        # add k for [a, b)
        if a <= left and right <= b:
            self.dat_a[k] += x
        elif left < b and a < right:
            self.dat_b[k] += (min(b, right) - max(a, left)) * x
            self._add(a, b, x, k * 2 + 1, left, (left + right) // 2)
            self._add(a, b, x, k * 2 + 2, (left + right) // 2, right)

    def _query_sum(self, a, b, k, left, right):
        if b <= left or right <= a:
            return 0
        elif a <= left and right <= b:
            return self.dat_a[k] + (right - left) * self.dat_b[k]
        else:
            res = (min(b, right) - max(a, left)) * self.dat_a[k]
            res += self._query_sum(a, b, k * 2 + 1, left, (left + right) // 2)
            res += self._query_sum(a, b, k * 2 + 2, (left + right) // 2, right)
            return res

    def add(self, a, b, x):
        return self._add(a, b, x, 0, 0, self.n)

    def query_sum(self, a, b):
        return self._query_sum(a, b, 0, 0, self.n)

    def return_value(self, a):
        return self.query_sum(a, a + 1)


def solve(n, d, a, xh_list):
    res = 0
    xh_list_s = sorted(xh_list, key=lambda x: x[0])
    x_list_s = [xh[0] for xh in xh_list_s]
    h_list_s = [xh[1] for xh in xh_list_s]

    sg = SegTree(list(range(n)), h_list_s)

    for i in range(n):
        v = sg.return_value(i)
        if v > 0:
            t = (v - 1) // a + 1
            res += t
            j = bisect_right(x_list_s, x_list_s[i] + 2 * d)
            sg.add(i, j, - t * a)
    return res


def main():
    n, d, a = map(int, input().split())
    xh_list = []
    for _ in range(n):
        x, h = map(int, input().split())
        xh_list.append((x, h))
    res = solve(n, d, a, xh_list)
    print(res)


def test():
    assert solve(3, 3, 2, [(1, 2), (5, 4), (9, 2)]) == 2
    assert solve(9, 4, 1, [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 2), (7, 3), (8, 4), (9, 5)]) == 5
    assert solve(3, 0, 1, [(300000000, 1000000000), (100000000, 1000000000), (200000000, 1000000000)]) == 3000000000


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
for i in range(n):
    h = xh[i][1]
    if h<=0:
        continue
    x = xh[i][0]
    j = i
    while j<n-1 and xh[j+1][0]<=x+2*d:
        j += 1
    for k in range(i,j+1):
        xh[k] = (xh[k][0], xh[k][1]-h)
    cnt += h
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])

ans = 0
for i,xh in enumerate(XH):
    X = xh[0]
    H = xh[1]
    if H > 0:
        num = ceil(H/A)
        for j in range(i,N):
            if XH[j][0] <= X+2*D:
                XH[j][1] -= A*num
            else:
                break
        ans += num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,d,a=map(int,input().split())
  l=[[0,0] for _ in range(n)]
  for i in range(n):
    x,h=map(int,input().split())
    l[i]=[x,(h+a-1)//a]
  l.sort()
  ans=0
  for i in range(n):
    [x,h]=l[i]
    if h>=0:
      for j in range(i+1,n):
        if l[j][0]>x+2*d:
          break
        else:
          l[j][1]-=h
      ans+=h
  print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]
  XH.sort(key=lambda x:x[0])
  #print(XH)

  B = []
  ans = 0
  for x,h in XH:
    BB = B[:]
    for s,t,c in BB:
      #print(s,t,c,x)
      if s <= x <= t:
        h -= A*c
      elif t < x:
        B.remove((s,t,c))
    #print(h)
    if h > 0:
      B.append((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
    #print(ans,x,x+2*D,(h+A-1)//A,B)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

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

ys = []
for _ in range(N):
    X, H = map(int, input().split())
    ys.append((X, 0, -(-H//A)))
    ys.append((X+2*D, 1, -(-H//A)))

ys.sort()
d1 = dict()
d2 = dict()
ls = []
c = 0
hs = [0]
for i, (y, f, h) in enumerate(ys):
    if f:
        d1[y-2*D] = c
    else:
        c += 1
        d2[y] = c
        ls.append(y)
        hs.append(h)

lls = []
for i in range(N):
    lls.append(d1[ls[i]]-d2[ls[i]]+1)

X = Bit(N+1)

r = 0
for i in range(N):
    n = lls[i]
    x = hs[i+1] + X.sum(i+1)
#    print(x,n)
    if x <=0:
        continue
    r += x
    X.add(i+1, -x)
    X.add(i+1+n, x)
print(r)

Submission status: Time Limit Exceeded

Solution code:
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)