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 operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size



from bisect import bisect_right
def resolve():
    N, D, A = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    X, _ = zip(*AB)
    D = 2*D

    seg = SegmentTree(N+10)
    ans = 0
    for i, (x, h) in enumerate(AB):
        h = -(-h // A)
        damage = seg.get(0, i+1)
        
        if h < damage:
            continue
        ans += h - damage
        seg.add(i, h-damage)
        seg.add(bisect_right(X, x + D), - h + damage)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()
    ans = 0
    for i in range(N):
        k = X[i]
        v = monster[k]
        if v <= 0:
            continue

        cnt = (v + A - 1) // A
        ans += cnt

        for j in range(i + 1, N):
            x = X[j]
            if k + 2 * D < x:
                break
            if monster[x] < 0:
                continue

            monster[x] -= A * cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()
    ans = 0
    for i in range(N):
        k = X[i]
        v = monster[k]
        if v <= 0:
            continue

        cnt = (v + A - 1) // A
        ans += cnt

        for j in range(i + 1, N):
            x = X[j]
            if k + 2 * D < x:
                break
            monster[x] -= A * cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

enems = []
for i in range(N):
  enemy = list(map(int, input().split()))
  enems.append(enemy)

# enemsをXをkeyとしてsort (nlogn)
# 貪欲法でx = X_i + Dとなるような位置で爆弾をH_0//A回投げてX_iの敵を倒す。これをi=0, 1, ...と繰り返す
enems.sort(key=lambda enemy: enemy[0])

res = 0

for i, enemy in enumerate(enems):
  # x = X_0 + D
  count = enemy[1] // A
  if enemy[1] % A:
    count += 1
  res += count
  
  # [X_0 - D, X_0 + D]の敵にもダメージを与える
  if count > 0:
    j = 1
    while i+j <N and enems[i+j][0] <= enemy[0] + 2*D:
      enems[i+j][1] -=count * A
      enems[i+j][1] = max(0, enems[i+j][1])
      j += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    if N == 1:
        print((monsters[0][1] + A - 1) // A)
        return
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

input=sys.stdin.readline

def main(args):
    n, d, a = map(int,input().split())
    
    monster = [0]*n
    pos = [0]*n
    for i in range(n):
        x, h = map(int,input().split())
        monster[i] = (x, h)
        pos[i] = x
    
    pos.sort()
    monster.sort()
    
    #print(pos)
    
    limit = [0]*n
    #そのモンスターを攻撃したとき巻き添えにできるやつらの中で一番右のヤツのindex
    for i in range(n):
        limit[i] = bisect.bisect_right(pos, pos[i]+2*d)-1
    #print(limit)
    
    damage = [0]*n
    ans = 0
    for i in range(n):
        HP = monster[i][1]
        attack = -(-max(0, (HP-a*damage[i]))//a)
        if attack > 0:
            ans += attack
            damage[i:limit[i]+1] = list(map(lambda x:x+attack, damage[i:limit[i]+1]))
        #print(damage)
    
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, d, a = map(int, input().split())
monster = [list(map(int, input().split())) for i in range(n)]
monster.sort(key=lambda x:x[0])
attackloc = list(map(lambda x:x[0]+d, monster ))
left =list(map(lambda x: max(x[0]-d,0), monster ))
damage=[0]*n
ans = 0
counter = 0
while counter<n:
  at = bisect.bisect_right(left, attackloc[counter])
  multi = (monster[counter][1]-damage[counter]-1)//a
  for i in range(counter, at):
    damage[i]+=a*(multi+1)
  ans+=multi+1
  counter+=1
  while counter <= n-1 and damage[counter]>=monster[counter][1]:
    counter+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, d, a = map(int, input().split())
monster = [list(map(int, input().split())) for i in range(n)]
monster.sort(key=lambda x:x[0])
attackloc = list(map(lambda x:x[0]+d, monster ))
left =list(map(lambda x: max(x[0]-d,0), monster ))
#right=[]
damage=[0]*n
#print(monster)
#print(attackloc)
#print(left)
ans = 0
counter = 0
while counter<n:
  at = bisect.bisect_right(left, attackloc[counter])
  multi = (monster[counter][1]-damage[counter])//a
  if  (monster[counter][1]-damage[counter])%a != 0:
    multi+=1
  #print(at)
  for i in range(counter, at):
    damage[i]+=a*multi
  ans+=multi
  while counter <= n-1 and damage[counter]>=monster[counter][1]:
    counter+=1
  #print(damage)
  #print(counter)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xi, hi = map(int, input().split())
    xh.append([xi, hi])

xh.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(xh[i][0])
    h.append(xh[i][1])

cnt = 0
for i in range(n):
    xi, hi = x[i], h[i]
    if hi == 0:
        continue
    else:
        num = (hi+a-1)//a
        cnt += num
    point = xi + 2*d
    left = i
    right = n
    while left+1 < right:
        mid = (left+right)//2
        if x[mid] <= point:
            left = mid
        else:
            right = mid
    for j in range(i, left+1):
        h[j] = max(0, h[j]-num*a)
print(cnt)

Submission status: Time Limit Exceeded

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

def main():
    n, d, a = map(int, input().split())
    XH = []
    for i in range(n):
        x, h = map(int, input().split())
        XH.append((x, h))

    XH.sort()
    from collections import deque
    q = deque()

    ans = 0
    import copy
    for x, h in XH:
        nq = deque()
        while q:
            r, s = q.popleft()
            if r+d < x:
                continue
            else:
                h -= s
                nq.append((r, s))
        #print(x, h)
        if h > 0:
            if h%a == 0:
                b = h//a
                ans += b
                nq.append((x+d, a*b))
            else:
                b = h//a+1
                ans += b
                nq.append((x+d, a*b))
        q = copy.copy(nq)
        #print(q)
        #print(ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

XH.sort()
from collections import deque
q = deque()

ans = 0
import copy
for x, h in XH:
    nq = deque()
    while q:
        r, s = q.popleft()
        if r+d < x:
            continue
        else:
            h -= s
            nq.append((r, s))
    #print(x, h)
    if h > 0:
        if h%a == 0:
            b = h//a
            ans += b
            nq.append((x+d, a*b))
        else:
            b = h//a+1
            ans += b
            nq.append((x+d, a*b))
    q = copy.copy(nq)
    #print(q)
    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    dam = list(accumulate(damage))
    if h[i]-dam[i] <= 0:
        continue
    bi = bisect.bisect(x,2*d+x[i])
    count = math.ceil((h[i]-dam[i])/a)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count

print(point)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from operator import itemgetter

readline= sys.stdin.readline
n,d,a=map(int,input().split())
xh=[list(map(int,readline().split())) for _ in range(n)]
xh.sort()
xh=np.array(xh)
x=xh[:,0]
h=xh[:,1]
start=0
i=0
while(1):
    if (start==n-1) and (h[start]<=0):
        break
    if h[start]<=0:
        start+=1
        continue
    #binary search
    if h[start]%a==0:
        times=h[start]//a
    else:
        times=h[start]//a+1
    left=start
    right=n-1
    mark=x[start]+2*d
    while(1):
        if right-left<=1:
            break
        mid=(left+right)//2
        if x[mid]>=mark:
            right=mid
        else:
            left=mid
    if x[right]<=mark:
        end=right
    else:
        end=left
    h[start:end+1]-=a*times
    i+=times
print(i)

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.sort()

cnt=0

for i in range(n):
    (x,h)=xh[i]
    if h>0:
        bomb=x+d

        count=((-1*h)//a)*(-1)
        damage=count*a
        cnt+=count
        j=1
        #print("bomb",bomb)
        while i+j<n and xh[i+j][0]<=bomb+d:
            xh[i+j][1]-=damage
            j+=1
            #print("?")

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from functools import lru_cache

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
x = np.array(x)
h = np.array(h)

# どこまで巻き込めるかを調査
search = np.searchsorted(x,2*d+x,side="right")-1

@lru_cache(maxsize=None)
def keisan():
    count = 0
    for i in range(n):
        if h[i] > 0:
            count += math.ceil(h[i]/a)
            h[i:search[i]+1] -= a*math.ceil(h[i]/a)
    return count

print(keisan())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
x = np.array(x)
h = np.array(h)

# どこまで巻き込めるかを調査
search = np.searchsorted(x,2*d+x,side="right")-1
count = 0

for i in range(n):
    if h[i] > 0:
        count += math.ceil(h[i]/a)
        h[i:search[i]+1] -= a*math.ceil(h[i]/a)

print(count)

Submission status: Time Limit Exceeded

Solution code:
"""
Given N, D, A, N means no. of monsters, D means distances of bombs, A attack of the bombs

Find the minimum of bombs required to win.

Each monster out of N pairs - pair[0] = position, pair[1] = health

hashmap[i] = H

pref

"""
from collections import deque

mod = 1e9+7
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    INF = 1e9 + 7
    N, D, A = [int(x) for x in raw_input().split()]
    D *= 2
    #monsters = []
    m = {}
    pref_sum = {}
    smallest_x = int(INF)
    biggest_x = 0
    for _ in range(N):
        pos, health = [int(x) for x in raw_input().split()]
        m[pos] = m.get(pos, 0) + health
        smallest_x = min(smallest_x, pos)
        biggest_x = max(biggest_x, pos)
        #monsters.append([pos, health])    
    
    remain_attack = 0
    ans = 0
    for cur in range(smallest_x, biggest_x+1):
        if cur in m and m[cur] > remain_attack:
            remained_health = m[cur] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            attack = times * A
            pref_sum[cur + D] = pref_sum.get(cur + D, 0) - attack
            remain_attack += attack
            ans += times
        remain_attack += pref_sum.get(cur, 0)
            
                
            
    
    """
    monsters.sort(key = lambda x : x[0])
    
    remain_attacks_queue = deque([])
    
    remain_attack = 0
    
    ans = 0
    
    for monster in monsters:
        # monster[0] - pos, monster[1] - health
        # queue[0] - position, queue[1] - attack points
        while len(remain_attacks_queue) and monster[0] - D > remain_attacks_queue[0][0]:
            remain_attack -= remain_attacks_queue.popleft()[1]
        if remain_attack < monster[1]:
            remained_health = monster[1] - remain_attack
            times = remained_health / A if remained_health % A == 0 else remained_health // A + 1
            #print(times)
            attack = times * A
            remain_attacks_queue.append([monster[0], attack])
            ans += times
            remain_attack += attack
    """
        
    print(ans)
    

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n,d,a=map(int,input().split())
m=[]
for i in range(n):
  m.append([])
  x,h=map(int,input().split())
  c=math.ceil(h/a)
  while a*c<h:
    c+=1
  m[-1].append(x)
  m[-1].append(c)
m=sorted(m, key=lambda student: student[0])
leftcursor=0
rightcursor=0

t=0
ans=0
while leftcursor<n:
  l=m[leftcursor][0]
  r=l+2*d
  t=m[leftcursor][1]
  ans+=t
  if rightcursor<n:
    while m[rightcursor][0]<=r:
      rightcursor+=1
      if rightcursor>=n:
        break
  for i in range(leftcursor,rightcursor):
    m[i][1]-=t
  while m[leftcursor][1]<=0:
    leftcursor+=1
    if leftcursor>=n:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

n, d, a = map(int, input().split())
m = []
x_list = []
for _ in range(n):
    x, h = map(int, input().split())
    m.append([x, (h+a-1)//a])
    x_list.append(x)
m.sort()
x_list.sort()

pos = m[0][0]
idx_start = 0
res = 0
while True:
    idx_end = bisect_right(x_list, pos+2*d) - 1
    for i in range(idx_start+1, idx_end+1):
        m[i][1] -= m[idx_start][1]
    res += m[idx_start][1]
    m[idx_start][1] = 0
    while idx_start < n and m[idx_start][1] <= 0:
        idx_start += 1
    if idx_start >= n:
        break
    pos = m[idx_start][0]

print(res)

Submission status: Time Limit Exceeded

Solution code:
N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
for i in range(N):
    if enemies[i][1] > 0:
        bomb = -(-enemies[i][1]//A)
        j = i
        while j < N and enemies[j][0]-enemies[i][0] <= 2*D:
            enemies[j][1] -= A*bomb
            j += 1
        ans += bomb

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

    for i, mi in enumerate(mon):
        if mi[1] <= 0:
            continue

        ans += mi[1]
        rb = mi[0] + 2 * d

        for mj in mon[i + 1:]:
            if mj[0] > rb:
                break

            mj[1] -= mi[1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    n, d, a = geta(int)
    mon = []
    ans = 0

    for _ in range(n):
        x, h = geta(int)
        mon.append([x, (h + a - 1) // a])

    mon.sort()

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

        ans += mon[i][1]
        rb = mon[i][0] + 2 * d

        for j in range(i + 1, n):
            if mon[j][0] > rb:
                break

            mon[j][1] -= mon[i][1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
    N,D,A = map(int, input().split())
    X,H = [0]*N,[0]*N
    tmp = [(0,0) for _ in range(N)]
    for i in range(N):
        tmp[i] = list(map(int, input().split()))
        tmp[i][0] -= 1
    # 座標順になるようにソートしておく
    tmp = sorted(tmp, key=lambda x:x[0])
    for i,l in enumerate(tmp): (X[i],H[i]) = l
    # 座標X[i]のモンスターはceil(H[i]/A)回攻撃すれば倒せる
    # N=5, D=2
    # 0 1 2 3 4 5 6 7 8 9 10
    # 0 5 0 2 0 0 3 3 0 0 4 (倒すのに必要な回数; 全部0にすれば終了)
    # 0 0 0 0 0 0 3 3 0 0 4 (座標3で5回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 1 (座標8で3回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 0 (座標10で1回爆破したあと)
    # ->よって5+3+1=9回が最小回数..?
    ans = 0
    for i in range(N):
        if sum(H)<=0: break
        if H[i]>0:
            # X[i]+Dで爆破を行う
            bomb = math.ceil(H[i]/A)
            ans += bomb
            for j,p in enumerate(X[i:]):
                if p<X[i]+2*D+1:
                    H[i+j] = max(0,H[i+j]-A*bomb)
                else:
                    break
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import math
def main():
    N,D,A = map(int, input().split())
    X,H = [0]*N,[0]*N
    tmp = [(0,0) for _ in range(N)]
    for i in range(N):
        tmp[i] = list(map(int, input().split()))
        tmp[i][0] -= 1
    # 座標順になるようにソートしておく
    tmp = sorted(tmp, key=lambda x:x[0])
    for i,l in enumerate(tmp): (X[i],H[i]) = l
    # 座標X[i]のモンスターはceil(H[i]/A)回攻撃すれば倒せる
    # N=5, D=2
    # 0 1 2 3 4 5 6 7 8 9 10
    # 0 5 0 2 0 0 3 3 0 0 4 (倒すのに必要な回数; 全部0にすれば終了)
    # 0 0 0 0 0 0 3 3 0 0 4 (座標3で5回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 1 (座標8で3回爆破したあと)
    # 0 0 0 0 0 0 0 0 0 0 0 (座標10で1回爆破したあと)
    # ->よって5+3+1=9回が最小回数..?
    ans = 0
    for i in range(len(X)):
        if sum(H)<=0: break
        if H[i]>0:
            # X[i]+Dで爆破を行う
            bomb = math.ceil(H[i]/A)
            ans += bomb
            for j,p in enumerate(X[i:]):
                if p<X[i]+2*D+1:
                    H[i+j] = max(0,H[i+j]-A*bomb)
                else:
                    break
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

n,d,a=map(int,input().split())
xl = []
hl = []
xhl =[]
for i in range(n):
    x,h = map(int,input().split())
    xhl.append([x,h])

xhl.sort()
#if xhl[0][1]<xhl[]
xl = [i[0] for i in xhl]
hl = [i[1] for i in xhl]
now = 0
cnt = 0

import bisect
while True:
    if now >= n:
        break
    if hl[now]==0:
        now+=1
        continue
    r = bisect.bisect_right(xl,xl[now]+2*d)
    bomb = max(math.ceil(hl[now]/a),0)
    hl[now] = 0
    #print(r)
    for i in range(now+1,r):
        if hl[i]==0:continue
        hl[i] = max(0,hl[i]-a*bomb)
    now += 1
    cnt += bomb

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

n,d,a=map(int,input().split())
xl = []
hl = []
xhl =[]
for i in range(n):
    x,h = map(int,input().split())
    xhl.append([x,h])

xhl.sort()
xl = [i[0] for i in xhl]
hl = [i[1] for i in xhl]
now = 0
cnt = 0

import bisect
while True:
    if now >= n:
        break
    if hl[now]==0:
        now+=1
        continue
    r = bisect.bisect_right(xl,xl[now]+2*d)
    bomb = max(math.ceil(hl[now]/a),0)
    hl[now] = 0
    #print(r)
    for i in range(now+1,r):
        hl[i] = max(0,hl[i]-a*bomb)
    now += 1
    cnt += bomb

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect

class BIT:
    def __init__(self, n, d = None):
        self.n = n
        self.bit = [0] * (n + 1)
        if d == None:
            return
        for i in range(n):
            self.update(i, d[i])

    #値更新
    def update(self, i, x = 1):
        i += 1
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    #区間合計値を出力            
    def query(self, i):
        i += 1
        res_sum = 0
        while i > 0:
            res_sum += self.bit[i]
            i -= i & -i
        return res_sum

N, D, A = list(map(int, input().split()))
pair_xh = [[-1, -1] for _ in range(N)] # 1回ずつしか使わないけどソートするから必要
for i in range(N):
    pair_xh[i][0], pair_xh[i][1] = list(map(int, input().split()))
pair_xh.sort(key = lambda x: x[0]) #座標でソート
 
# q_lim_d = deque() # 累積和に含まれる攻撃範囲とダメージを保存する場所
# total = 0 # 喰らいダメージの累積和
count = 0 # 攻撃回数
bit = BIT(N + 1)

for i in range(N):
    x = pair_xh[i][0]
    h = pair_xh[i][1]
    
    # while len(q_lim_d) and q_lim_d[-1][0] < x: # 範囲外になったら喰らわないから累積和から外す
    #     total -= q_lim_d[-1][1]
    #     q_lim_d.pop()
    # h -= total
    h -= bit.query(i)
    if h > 0: # 見てる敵の体力が0になる攻撃回数を求めその分を累積和に足す
        times = (h + A - 1) // A # 0にするのに必要な回数(切り上げ)
        count += times
        damage = A * times
        # total += damage
        # q_lim_d.appendleft([x + 2 * D, damage])
        bit.update(i, damage)
        rx = x + D * 2
        j = bisect.bisect_right(pair_xh, [rx + 1, -1])
        bit.update(j, -damage)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

def main():
  N, D, A = map(int, input().split())
  D2 = 2 * D
  XH = [[0, 0] for _ in range(N)]
  for i in range(N):
    XH[i][0], Hi = map(int, input().split())
    XH[i][1] = (Hi-1)//A + 1

  XH.sort()
  X = [i[0] for i in XH]
  H = [i[1] for i in XH]
  l = 0
  r = bisect_right(X, X[0]+D2)
  ans = 0
  while r < N:
    if X[r]-X[r-1] > D2:
      ans += max(H[l:r])
      l = r
      r = bisect_right(X, X[l]+D2)
      continue
    Hl = H[l]
    ans += Hl
    first = True
    nxl = l
    for i in range(l, r):
      H[i] -= Hl
      if (H[i]>0) and first:
        nxl = i
        first = False
    if first:
      l = r
    else:
      l = nxl
    r = bisect_right(X, X[l]+D2)

  ans += max(H[l:])
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

def main():
  N, D, A = map(int, input().split())
  D2 = 2 * D
  XH = [[0, 0] for _ in range(N)]
  for i in range(N):
    XH[i][0], Hi = map(int, input().split())
    XH[i][1] = (Hi-1)//A + 1

  XH.sort()
  X = [i[0] for i in XH]
  H = [i[1] for i in XH]
  l = 0
  r = bisect_right(X, X[0]+D2)
  ans = 0
  while r < N:
    Hl = H[l]
    ans += Hl
    first = True
    nxl = l
    for i in range(l, r):
      H[i] -= Hl
      if (H[i]>0) and first:
        nxl = i
        first = False
    if first:
      l = r
    else:
      l = nxl
    r = bisect_right(X, X[l]+D2)

  ans += max(H[l:])
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

def main():
  N, D, A = map(int, input().split())
  D2 = 2 * D
  XH = [[0, 0] for _ in range(N)]
  for i in range(N):
    XH[i][0], Hi = map(int, input().split())
    XH[i][1] = (Hi-1)//A + 1

  XH.sort()
  X = [i[0] for i in XH]
  H = [i[1] for i in XH]
  l = 0
  r = bisect_right(X, X[0]+D2)
  ans = 0
  while r < N:
    Hl = H[l]
    ans += Hl
    first = True
    nxl = l
    for i in range(l, r):
      H[i] -= Hl
      if (H[i]>0) and first:
        nxl = i
        first = False
    if first:
      l = r
    else:
      l = nxl
    r = bisect_right(X, X[l]+D2)

  ans += max(H[l:])
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
D2 = 2 * D
XH = [[0, 0] for _ in range(N)]
for i in range(N):
  XH[i][0], Hi = map(int, input().split())
  XH[i][1] = (Hi-1)//A + 1
  
XH.sort()
X = [i[0] for i in XH]
H = [i[1] for i in XH]
l = 0
r = bisect_right(X, X[0]+D2)
ans = 0
while r < N:
  Hl = H[l]
  ans += Hl
  first = True
  nxl = l
  for i in range(l, r):
    H[i] -= Hl
    if (H[i]>0) and first:
      nxl = i
      first = False
  if first:
    l = r
  else:
    l = nxl
  r = l + bisect_right(X[l:], X[l]+D2)

ans += max(H[l:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N, D, A = map(int, input().split())
D2 = 2 * D
XH = [[0, 0] for _ in range(N)]
for i in range(N):
  XH[i][0], Hi = map(int, input().split())
  XH[i][1] = (Hi-1)//A + 1
  
XH.sort()
X = [i[0] for i in XH]
H = [i[1] for i in XH]
l = 0
r = bisect_right(X, X[0]+D2)
ans = 0
while r < N:
  Hl = H[l]
  ans += Hl
  first = True
  nxl = l
  for i in range(l, r):
    H[i] -= Hl
    if (H[i]>0) and first:
      nxl = i
      first = False
  if nxl == l:
    l = r
  else:
    l = nxl
  r = bisect_right(X, X[l]+D2)

ans += max(H[l:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, d, a = list(map(int, readline().split()))
    xh = [list(map(int, readline().split())) for _ in range(n)]

    from operator import itemgetter
    import bisect

    xh.sort(key=itemgetter(0))
    coordinate = [xh[i][0] for i in range(n)]
    hp = [xh[i][1] for i in range(n)]

    ans = 0

    for i in range(n):
        x = coordinate[i]
        h = hp[i]

        if h > 0:
            num = (h + a - 1) // a
            ans += num
            dmg = a * num
            range_left = x
            range_right = x + 2 * d
            index_left = bisect.bisect_left(coordinate, range_left)
            index_right = bisect.bisect_right(coordinate, range_right)
            for j in range(index_left, index_right):
               hp[j] -= dmg

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,D,A=map(int,input().split())
from heapq import heappop,heappush,heapify
B=[]
for _ in range(N):
    x,h=map(int,input().split())
    B.append((x,h))
heapify(B)

c=0
while B:
    x,h=heappop(B)
    sup=x+2*D
    bomb=(h-1)//A+1
    temp=[]
    c+=bomb
    while B:
        X,H=heappop(B)
        if X<=sup:
            H=max(0,H-A*bomb)
            if H>0:
                temp.append((X,H))
        else:
            temp.append((X,H))
            break
    for t in temp:
        heappush(B,t)
print(c)