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 heapq import heappop,heappush
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=heappop(xh)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  pappend=pool.append
  while True:
    if not xh:
      break
    y,z=heappop(xh)
    if y <= t:
      if z>b:
        z-=b
        pappend((y,z))
    else:
      pappend((y,z))
      break
  for i in pool:
    heappush(xh,i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

n, d, a = map(int,input().split())
xhlist=[]
for i in range(n):
    x, h = map(int,input().split())
    h=math.ceil(h/a)
    xhlist.append([x, h])

xhlist=sorted(xhlist)
xlist=[]
hlist=[]
for xhl in xhlist:
    xlist.append(xhl[0])
    hlist.append(xhl[1])

now=0
turn=0
memory=0

while now<n:
    swit=0
    pos=xlist[now]+d
    atk=hlist[now]
    if memory>0:
        hani=bisect_right(xlist, pos+d, lo=memory)
    else:
        hani=bisect_right(xlist, pos+d)
    if hani!=n:
        memory=hani
        tasu=0
        turn+=atk
        sa=hani-now
        for i in range(sa):
            if now+i<n:
                if hlist[now+i]>0:
                    hlist[now+i]-=atk
                if swit==0:
                    if hlist[now+i]<=0:
                        tasu+=1
                    else:
                        swit=1
        now+=tasu
    else:
        turn+=max(hlist[now:])
        now+=n
    
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, di, a = LI()
    xs = []
    d = {}
    q = []
    for i in range(n):
        x, h = LI()
        xs.append(x)
        if h % a == 0:
            d[x] = h // a
        else:
            d[x] = h // a + 1
    sorted_xs = sorted(xs)
    ans = 0
    for i in range(n):
        if d[sorted_xs[i]] < 1:
            continue
        else:
            ans += d[sorted_xs[i]]
            while True:
                j = 0
                if i + j >= n:
                    break
                if sorted_xs[i + j] <= sorted_xs[i] + 2 * di:
                    d[sorted_xs[i + j]] -= d[sorted_xs[i]]
                else:
                    break
                j += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
H = list(H)
K = [-(-i//a) for i in H]
now = 0
ans = 0
for now in range(n):
  l = K[now]
  if l > 0:
    ans += l
    for i in range(now, bisect.bisect_right(X, X[now]+2*d)):
      K[i] -= l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,d,a=map(int,input().split())
xh=[tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
ans=0
while xh:
  x,h=heapq.heappop(xh)
  c=h//a+bool(h%a)
  b=a*c
  ans+=c
  t=x+2*d
  pool=[]
  while True:
    if not xh:
      break
    y,z=heapq.heappop(xh)
    if y <= t:
      if z>b:
        z-=b
        pool.append((y,z))
    else:
      pool.append((y,z))
      break
  for i in pool:
    heapq.heappush(xh,i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, D, A = map(int, input().split())
X = [0 for _ in range(N)]
H = [0 for _ in range(N)]
for i in range(N):
    x, h = map(int, input().split())
    X[i] = x
    H[i] = h
M = sorted(zip(X, H), key=lambda x: x[0])
left = 0
irn = [0 for _ in range(N)]
for right in range(N):
    while M[right][0] - M[left][0] > 2*D:
        left += 1
    irn[right] = right - left

Bomb = [0 for _ in range(N)]
Bomb[0] = (M[0][1]-1)//A+1
for i in range(1, N):
    Bomb[i] = max((M[i][1]-1)//A - sum(Bomb[i-irn[i]:i]) + 1, 0)
print(sum(Bomb))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import floor, ceil

n, d, a = map(int, input().split())
l = sorted([list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)], key=lambda x: x[0])
cnt = 0

for i in range(n):
  if l[i][1] <= 0:
    continue

  num = ceil(l[i][1] / a)
  dam = num * a
  cnt += num
  for j in range(n):
    if l[j][0] > l[i][0] + (2 * d):
      break

    l[j][1] -= dam

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
H = list(H)
now = 0
ans = 0
for now in range(n):
  if H[now] > 0:
    l = -(-H[now]//a)
    ans += l
    l *= a
    for i in range(now, bisect.bisect_right(X, X[now]+2*d)):
      H[i] -= l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,d,a = list(map(int,input().split()))
xh = [list(map(int,input().split())) for i in range(n)]
from math import ceil
xh.sort()
for i in range(n):
    xh[i][1] = ceil(xh[i][1]/a)

cursor = 0
cur_l = xh[0][0]
def update(l,dec):
    for i,(x,h) in enumerate(xh):
        if x <= (l+d*2):
            xh[i][1]-=dec
        else:
            return
ret = 0
while True:
    if cursor==n:
        break
    cur_l,dec = xh[cursor]
    if dec > 0:
        update(cur_l,dec)
        ret+=dec
    cursor+=1
print(ret)

Submission status: Time Limit Exceeded

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

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

print(ans)
# print(hp_dict)

Submission status: Time Limit Exceeded

Solution code:
from math import *
import bisect
n, d, a = map(int, input().split())
p = []
for _ in range(n):
  p.append(tuple(map(int, input().split())))

p = sorted(p)
c=0
for i in range(n):
  x, h = p[i]
  if h <= 0: continue
  m = ceil(h/a)
  c+=m
  m = m*a
  for i in range(i+1, n):
    if x + d*2 < p[i][0]:
      break
    p[i] = (p[i][0], p[i][1] - m)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, d, a = map(int, input().split())
xh = []
x_list = []
for i in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
    x_list.append(x)
xh.sort()
x_list.sort()
count = 0
min_x = 0
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    flag = True
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    for i in range(min_x, bisect.bisect(x_list, place + d)):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            if flag == True:
                min_x += 1
        else:
            flag = False
        xh[i][1] = new_h
print(count)

Submission status: Time Limit Exceeded

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

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

print(ans)
# print(hp_dict)

Submission status: Time Limit Exceeded

Solution code:
import sys
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])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


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:
N, D, A=(int(i) for i in input().split())
P=[[int(i) for i in input().split()] for  _ in range(N)]
P=sorted(P, key=lambda x:x[0])

ans=0

for i in range(N):
    if P[i][1]>0:
        if P[i][1]%A==0:
            bomb=P[i][1]//A
        else:
            bomb=P[i][1]//A+1
        ans+=bomb
        for j in range(i,N):
            if P[j][0]<=P[i][0]+2*D:
                P[j][1]-=A*bomb
            else:
                break
print(ans)

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()]

def main():
    N,D,A = LI()
    M = []
    for i in range(N):
        M.append(LI())
    M.sort(key = lambda x: x[0])
    
    count = 0
    for i in range(N):
        if M[i][1] > 0:
            bomb = (M[i][1]+A-1)//A
            count += bomb
            damage = bomb * A
            for j in range(i,N):
                if M[j][0] <= M[i][0] + 2*D:
                    M[j][1] -= damage
                else:
                    break

    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N,D,A = inputMap()
	Xmin = float('inf')
	Xmax = 0
	XH = []
	for i in range(N):
		X,H = inputMap()
		XH.append((X,H))
		if X < Xmin:
			Xmin = X
		if X > Xmax:
			Xmax = X

	XH.sort()
	ans = 0

	while True:
		#print(XH)
		if len(XH) == 0:
			break

		X,H = XH[0]
		eikyou = X+(2*D)
		#print(eikyou)

		tmp = -(-H // A)
		ans += tmp
		XH = XH[1:]

		delll = []
		cng = []
		for i,val in enumerate(XH):
			X,H = val
			if X > eikyou:
				break

			H -= tmp * A
			if H <= 0:
				delll.append(val)
			else:
				XH[i] = (X,H)

		for i in delll:
			XH.remove(i)


	print(ans)




if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

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

    for i in range(N):
        x, h = map(int, input().split())
        B.append((x,h))

    B.sort()
    X = [0] * N
    H = [0] * N
    for i in range(N):
        X[i], H[i] = B[i]
    ans = 0
    ok = [False] * N


    for i in range(N):
        if ok[i]:
            continue
        cnt = H[i] // A if H[i] % A == 0 else H[i] // A + 1
        ans += cnt
        ok[i] = True
        search_max = bisect_right(X, X[i] + 2 * D) - 1
        for j in range(min(i+1,N),min(search_max+1,N)):
            if ok[j]:
                continue
            H[j] -= cnt * A
            if H[j] <= 0:
                ok[j] = True
    
    print(ans)



if __name__ == "__main__":
    main()

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(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
            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 count

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

    print(check(M))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from bisect import bisect_right


def solve(*args: str) -> str:
    n, d, a = map(int, args[0].split())
    XH = [tuple(map(int, s.split())) for s in args[1:]]
    XH.sort()
    X, H = map(list, zip(*XH))

    count = 0
    pj = 0
    for i, x in enumerate(X):
        if H[i] <= 0:
            continue

        pj = j = bisect_right(X, x+(2*d), lo=pj)
        m = H[i]//a + (1 if 0 < H[i] % a else 0)
        count += m
        for k in range(i, j):
            H[k] -= a*m

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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])
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
i = 0
while i <= n:
    left = i # 可能
    right = n # 不可能
    while left+1 < right:
        mid = (left + right) // 2
        if x[mid] - x[i] <= 2*d:
            left = mid
        else:
            right = mid
    cnt += h[i]
    hiku = h[i]
    bit = 0
    next_i = i
    for j in range(i, left+1):
        h[j] -= hiku
        if bit == 0 and h[j] > 0:
            next_i = j
            bit = 1
    if next_i == i:
        i = left + 1
    else:
        i = next_i

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
            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:
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 - 1)
        self.dat_b = [0] * (self.n * 2 - 1)
        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, k, left, right):
        if left == a and right == a + 1:
            return self.dat_a[k]
        elif a < (left + right) // 2:
            return self.dat_a[k] + self._return_value(a, k * 2 + 1, left, (left + right) // 2)
        else:
            return self.dat_a[k] + self._return_value(a, k * 2 + 2, (left + right) // 2, right)

    def return_value(self, a):
        return self._return_value(a, 0, 0, self.n)


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:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, di, a = LI()
    xs = []
    d = {}
    q = []
    for i in range(n):
        x, h = LI()
        xs.append(x)
        if h % a == 0:
            d[x] = h // a
        else:
            d[x] = h // a + 1
    sorted_xs = sorted(xs)
    ans = 0
    for i in range(n):
        if d[sorted_xs[i]] < 1:
            continue
        else:
            ans += d[sorted_xs[i]]
            for j in range(1, n):
                if i + j >= n:
                    break
                if sorted_xs[i + j] <= sorted_xs[i] + 2 * di:
                    d[sorted_xs[i + j]] -= d[sorted_xs[i]]
                else:
                    break
    print(ans)




if __name__ == '__main__':
    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)):
  while Harr[i] > 0:
    a = bisect.bisect_right(arr, int(arr[i])+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:
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][0]+D>=P[j][0]-D):
                P[j][1]=P[j][1]-P[i][1]
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

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

x = [0] * n
h = [0] * n



for i in range(n):
    x[i], h[i] = map(int, input().split())

s = sorted(zip(x, h))

x = [k for k, _ in s]

x_next = list(range(1,n))
x_prev = list(range(0,n-1))
x_next.append(None)
x_prev.insert(0,None)

h = [k for _, k in s]


cus = 0
total = 0
while cus is not None and cus < n:
    bd = x[cus] + d
    t = math.ceil(h[cus] / a)
    h[cus] = 0
    total += t
    m = t * a

    j = x_next[cus]
#    print(cus)
    if j is None:
        break
    #print(j)
    while j is not None and x[j] <= bd + d:

        h[j] -= m
        if h[j] <= 0:
            prev_j = x_prev[j]
            next_j = x_next[j]
            if prev_j is not None:
                x_next[prev_j] = next_j
            if next_j is not None:
                x_prev[next_j] = prev_j
        j = x_next[j]

    if x_next[cus] is not None:
        x_prev[x_next[cus]] = None
        cus = x_next[cus]


print(total)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from bisect import bisect_right


def solve(*args: str) -> str:
    n, d, a = map(int, args[0].split())
    XH = [tuple(map(int, s.split())) for s in args[1:]]
    XH.sort()
    X, H = map(list, zip(*XH))

    count = 0
    for i, x in enumerate(X):
        if H[i] <= 0:
            continue

        j = bisect_right(X, x+(2*d))
        m = H[i]//a + (1 if 0 < H[i] % a else 0)
        count += m
        for k in range(i, j):
            H[k] -= a*m

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
import math
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:
import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
count = 0
min_x = 0
x = [xh[i][0] for i in range(n)]
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    flag = True
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    for i in range(min_x, bisect.bisect(x, place + d)):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            if flag == True:
                min_x += 1
        else:
            flag = False
        xh[i][1] = new_h
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

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

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


#bの倍数の中でaを超える最小
def calc(a,b):
    return math.ceil(a/b)*b

ans=0
for i in range(N):
    if H[i]>0:
        bom=X[i]+D
        Lb=i
        Rb=bisect.bisect_right(X,bom+D)
        ans+=H[i]//A
        if H[i]%A!=0:
            ans+=1
        dam=calc(H[i],A)
        for j in range(Lb,Rb):
            H[j]-=dam
        
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])
    imin = N
    for i in range(cur,ind):
        X[i][1] -= n*A
        if X[i][1]>0:
            imin = min(imin,i)
    cnt += n
    if imin<N:
        cur = imin
    else:
        flag = 0
        for i in range(ind,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())
x_b = []
x_b2 = []
x = [0]*n
h_b = []
h = [0]*n
for i in range(n):
    x_temp,h_temp = map(int,input().split())
    x_b.append({'key':i, 'val':x_temp})
    x_b2.append(x_temp)
    h_b.append(h_temp)

x_b.sort(key = lambda x_b : x_b['val'])

for i in range(n):
    ind = x_b[i]['key']
    x[i] = x_b2[ind]
    h[i] = h_b[ind]

ans = 0
for i in range(n):
    if (h[i] <= 0):
        continue
    at_num = ((h[i] -1 )// a) + 1
    ans += at_num
    h[i] -= at_num * a
    x_origin = x[i]
    while(True):
        i += 1
        if(i >= n):
            break
        if(x_origin + 2*d >= x[i]):
            h[i] -= at_num * a
        else:
            break

print(ans)

Submission status: Time Limit Exceeded

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

from math import ceil

monsters = []
for _ in range(N):
    X, h = map(int, input().split())
    monsters.append((X, h))

monsters.sort()

def bombing_campain(monsters, alive_i, bombing_x, N, D, A):
    num_bombs = ceil(monsters[alive_i][1] / A)
    dmg = A * num_bombs
    
    for i in range(alive_i, N):
        m = monsters[i]

        if m[0] <= bombing_x + D:
            monsters[i] = (m[0], max(monsters[i][1] - dmg, 0))
        else:
            break

    next_i = alive_i
    for i in range(alive_i, N):
        if monsters[i][1] == 0:
            next_i = i
        else:
            break
    
    return num_bombs, next_i+1



def solve(monsters, N, D, A):
    alive_i = 0
    num_bombs = 0

    while alive_i < N:
        alive_x = monsters[alive_i][0]
        bombing_x = alive_x + D

        nb, alive_i = bombing_campain(monsters, alive_i, bombing_x, N, D, A)
        num_bombs += nb

    return num_bombs

 
print(solve(monsters, N, D, A))

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 hp_dict[index] <= 0:
        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
            kari_place = place_dict[k][1]
            if hp_dict[kari_place] <= 0:
                continue
            else:
                hp_dict[kari_place] -= bomb * A


print(ans)
# print(hp_dict)

Submission status: Time Limit Exceeded

Solution code:
M,D,A = map(int,input().split())

L = [list(map(int,input().split())) for _ in range(M)]
# print(type(max(L)[0]))

SU = [0 for _ in range(max(L)[0])]

# トータルの回数
ans = 0

for i in range(M):
    SU[L[i][0]-1] = L[i][1]

# print(SU)

# 最初に0意外の数が出てくるインデックスを返す関数
# すべて0なら-1を返す
def notzero():
    for j in range(len(SU)):
        if SU[j] != 0:
            return j
    return -1
# print(notzero())

# SUのインデックスSからG-1までをA減らす関数
# GがSUの範囲を越えていないかチェック
def delA(S,G):
    if G > len(SU):
        G = len(SU)
    for k in range(S,G):
        if SU[k] >= A:
            SU[k] -= A
        else:
            SU[k] = 0

F = notzero()
while F != -1:
    ans += 1
    delA(F,F+2*D+1)
    F = notzero()


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 = set()
  ans = 0
  for x,h in XH:
    BB = set()
    for s,t,c in B:
      #print(s,t,c,x)
      if s <= x <= t:
        h -= A*c
        BB.add((s,t,c))
    #print(h)
    if h > 0:
      BB.add((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:
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]

XH = sorted(XH)

ans = 0
nw = 0
mm = 0
cst = 0
while(1):
    mm = XH[nw][0]+2*D
    cst = ((XH[nw][1]-1)//A)+1
    ans += cst

    con = True
    con2 = True
    for i in range(nw+1,N):
        if XH[i][0] <= mm:
            XH[i][1] -= cst*A
        else:
            break

        if XH[i][1] <= 0 and con:
            nw = i+1
            con2 = False
        else:
            con = False
    
    if con2:
        nw += 1
    if nw >= N:
        break
    

print(ans)